我的算法书 - Range Count Query

题目解析

1 核心解题思路

题目要求查询在原数组 $A$ 的区间 $\left[L,R\right]$ 内，数值 $X$ 出现了多少次。

我的代码将原问题转化为了二维点查找问题的一个变种，具体步骤如下：

数据重组：将原数组的每个元素转化成二元组 (数值, 原下标)。
全局排序：将这些二元组按照 数值第一关键字、原下标第二关键字 进行升序排序。
- 排序后，所有数值为 $X$ 的元素会聚在一起，形成一个连续的块。
- 在这个块内部，元素的“原下标”是有序的。
四次二分查找：
- 先通过数值 $X$ ，找到它在排序后数组中的起始位置和结束位置（划定数值范围）。
- 在上述范围内，再通过原下标 $L$ 和 $R$ ，找到符合条件的元素个数（划定下标范围）。

2 代码详细拆解

A. 数据结构与预处理 (Init)

struct node {
    int val; // 数值
    int pos; // 原数组中的下标
} a[maxn];

bool compare(node & a ,node &b) {
    if( a.val == b.val) {
        return a.pos < b.pos; // 数值相同，按下标排序
    }
    return a.val < b.val;     // 否则按数值排序
}

作用：这不仅让相同的 $X$ 靠在一起，还保证了它们内部是按下标递增的。这就为后续对 pos 进行二分查找创造了单调性条件。

B. 手写二分查找函数

代码中手写了两个 lower_bound / upper_bound 风格的函数。

bs_find_g(l, r, val):
- 功能：在排序后的数组中，寻找第一个 val 大于传入参数 val 的位置。
- 用途：用来确定数值 $X$ 在数组 a 中的左右边界。
bs_find_pos(l, r, pos):
- 功能：在指定的区间 [l, r) 内（此时该区间内所有元素的 val 都相同），寻找第一个 pos 大于传入参数 pos 的位置。
- 用途：在数值已经确定为 $X$ 的范围内，筛选出原下标在 $\left[L,R\right]$ 之间的元素。

C. 查询逻辑 (Query Processing)

这是代码中最精彩的部分，对于每个查询 $L,R,X$ ：

// 1. 确定数值 X 的“地盘”
// 找到第一个 val >= x 的位置 (等同于寻找 > x-1 的位置)
int L = bs_find_g(1, n+1, x-1);

// 如果找不到，或者找到的位置数值不是 X，说明数组里根本没有 X
if( L == n+1 || a[L].val != x) {
    cout << 0 << "\n";
    continue;
}

// 找到第一个 val > x 的位置
int R = bs_find_g(1, n+1, x);

此时，排序后的数组 a 中，下标区间 [L, R) (左闭右开) 内的所有元素，其 val 都等于 $X$ 。

// 2. 在 X 的“地盘”里，筛选原下标 [l, r]
// 在区间 [L, R) 中，找到第一个原下标 pos >= l 的位置
int ll = bs_find_pos(L, R, l-1);

// 在区间 [L, R) 中，找到第一个原下标 pos > r 的位置
int rr = bs_find_pos(L, R, r);

// 3. 计算数量
cout << rr - ll << "\n";

因为 [L, R) 区间内 pos 是有序的，rr 是大于 $R$ 的第一个位置，ll 是大于等于 $L$ 的第一个位置，两者相减 rr - ll 即为原下标在 $\left[L,R\right]$ 范围内的元素个数。

3 算法复杂度分析

时间复杂度：
- 预处理：排序消耗 $O\left(N\log N\right)$ 。
- 查询：每次查询进行了 4 次二分查找。每次二分的时间是 $O\left(\log N\right)$ 。总查询时间为 $O\left(Q\log N\right)$ 。
- 总时间： $O\left(\left(N+Q\right)\log N\right)$ 。这完全可以通过 $2\times 10^{5}$ 的数据规模。
空间复杂度：
- $O\left(N\right)$ ，用于存储结构体数组。相比于 vector<int> idx[maxn] 的邻接表写法，这种写法内存更加紧凑且连续，常数更小。

4 举例演示

假设输入：

N = 5
A = [3, 1, 4, 1, 5]
Query: L=1, R=4, X=1

1 预处理后 a 数组的状态：

排序后索引	`a[i].val`	`a[i].pos`
1	1	2
2	1	4
3	3	1
4	4	3
5	5	5

2 处理查询 L=1, R=4, X=1：

定值域：
- bs_find_g(..., 0) 找第一个 val >= 1 $\to$ 返回索引 1 (L).
- bs_find_g(..., 1) 找第一个 val > 1 $\to$ 返回索引 3 (R).
- 锁定区间 [1, 3)，即索引 1 和 2。
定下标：
- 在索引 [1, 3) 中，找第一个 pos >= 1 $\to$ 索引 1 的 pos 是 2 (满足)，返回 1 (ll).
- 在索引 [1, 3) 中，找第一个 pos > 4 $\to$ 索引 1 pos=2 (不满足)，索引 2 pos=4 (不满足)。循环结束返回 3 (rr).
计算：
- ans = rr - ll = 3 - 1 = 2。
- 原数组中下标 1 到 4 之间确实有两个 1 (分别在原下标 2 和 4)。

总结

代码是一个标准的“静态二维数点”问题的解法。

代码

cpp

copy

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

        /*
 * Author by Rainboy blog: https://blog.roj.ac.cn github : https://github.com/rainboylvx
 * date: 2025-12-24 14:36:17
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
struct node {
    int val;
    int pos;
} a[maxn];

bool compare(node & a ,node &b) {
    if( a.val == b.val) {
        return a.pos < b.pos;
    }
    return a.val < b.val;
}
//这是最快的写法
int mid(int l,int r) { return (l+r) >> 1; }


// 第一个 >val 的位置
// 第一个>4 的位置,就是第一个>=5的位置
int bs_find_g(int l,int r,int val) {
    while( l < r) {
        int m = mid(l,r);
        if( a[m].val > val ) //成立
            r = m;
        else //不成立,抛弃左半边
            l = m+1;
    }
    return l ;
}

//只比较位置
int bs_find_pos(int l,int r,int pos) {
    while( l < r) {
        int m = mid(l,r);
        if( a[m].pos > pos ) //成立
            r = m;
        else //不成立,抛弃左半边
            l = m+1;
    }
    return l ;
}


void init(){
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int t;
        std::cin >> t;
        a[i].pos = i;
        a[i].val = t;
    }
    std::sort(a+1,a+1+n,compare);
    // for(int i = 1;i <= n ;++i ) printf("%d ",a[i].pos);
    // printf("\n");
    // for(int i = 1;i <= n ;++i ) printf("%d ",a[i].val);
    // printf("\n");
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    
    init();
    int T;
    std::cin >> T;
    while (T--) {
        int l,r,x;
        std::cin >> l >> r >> x;
        
        // 找到第一个 val >= x 的位置
        int L = bs_find_g(1, n+1, x-1);
        if( L == n+1 || a[L].val != x) {
            std::cout << 0 << "\n";
            continue;
        }

        //第一个 > x 的位置
        int R = bs_find_g(1, n+1,x);

        //第一个>= l的位置
        int ll = bs_find_pos(L, R, l-1);

        //第一个> r的位置
        int rr = bs_find_pos(L, R, r);
        std::cout << rr- ll << "\n";
    }

    return 0;
}

目录