题目描述

难度分:$793$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n)$，下标从$1$开始。

然后输入$q$个询问，每个询问输入$L,R(1 \leq L \leq R \leq n)$和$x(1 \leq x \leq n)$。

对每个询问，输出有多少个下标$i$在$[L,R]$内的$a[i]$，满足$a[i]=x$。

输入样例

5
3 1 4 1 5
4
1 5 1
2 4 3
1 5 2
1 3 3

输出样例

2
0
0
1

算法

二分查找

先用哈希表构建映射“值 $\rightarrow$ 出现的索引列表”$val2pos$，然后对于每个查询$(l,r,x)$，二分查找$x$在列表$val2pos[x]$中的出现范围即可。即第一个大于等于$l$的位置$j$，第一个大于$r$的位置$k$，$k-j$就是$x$在子数组$[l,r]$出现的次数。

复杂度

时间复杂度

遍历一遍数组将不同值的索引进行分组时间复杂度是$O(n)$，对于每个$query$，二分查找确定范围时间复杂度是$O(log_2n)$的，因此算法的整体时间复杂度为$O(n+qlog_2n)$。

空间复杂度

开辟了一个哈希表对数组中的元素按值分组，一共存了$O(n)$规模的索引，最差情况下数组中都是各不相同的值，存了$2n$级别的元素，额外空间复杂度仍然是$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <array>
#include <vector>
#include <unordered_map>

using namespace std;
const int N = 200010;
int a[N], n;

int main() {
    scanf("%d", &n);
    unordered_map<int, vector<int>> val2pos;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        val2pos[a[i]].push_back(i);
    }
    int q;
    scanf("%d", &q);
    while(q--) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        auto& v = val2pos[x];
        int j = lower_bound(v.begin(), v.end(), l) - v.begin();
        int k = upper_bound(v.begin(), v.end(), r) - v.begin();
        printf("%d\n", max(0, k - j));
    }
    return 0;
}