序列,多次查询区间中有多少不同的数
\(1\leq n, m, a_i\leq10^6, 1\leq l\leq r\leq n\)
solution
这题把莫队卡了? 好像有dalao用莫队卡常过了,莫队是啥,早忘咋写了 = =
本蒟蒻只会用树状数组
根据询问查找题目中一些特殊的性质
由于询问的是区间的种类数,所以只需要每个数在该区间出现一次就够了
所以我们只关心每个数在区间中最后一次出现的位置
对询问离散化,把它们按照右端点排序,然后扫一遍,开一个树状数组把新出现的颜色种类++,重复出现的颜色种类--,显然树状数组的添加是动态的,不能一次性就建好,所以开一个指针,每次询问都把指针移到右端点,并把路径上的点加入到树状数组中就好了
code
/*
work by:Ariel_
*/
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int N = 1e6 + 5;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
map<int, int>last;
int n, tree[N], a[N], m, Ans[N], p = 1;
struct Node{int l, r, id;}A[N];
void Insert(int x, int k) {
for (int i = x; i <= n; i += i & (-i)) tree[i] += k;
}
int Query(int x) {
int res = 0;
for (int i = x; i; i -= i & (-i)) res += tree[i];
return res;
}
bool cmp(Node x, Node y) {
if (x.r == y.r) return x.l < y.l;
return x.r < y.r;
}
int main(){
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
m = read();
for (int i = 1; i <= m; i++)
A[i].l = read(), A[i].r = read(), A[i].id = i;
sort(A + 1, A + m + 1, cmp);
for (int i = 1; i <= m; i++) {
while (p <= A[i].r) {
if (last[a[p]]) Insert(last[a[p]], -1);
Insert(last[a[p]] = p, 1);
p++;
}
Ans[A[i].id] = Query(A[i].r) - Query(A[i].l - 1);
}
for (int i = 1; i <= m; i++) printf("%d\n", Ans[i]);
puts("");
return 0;
}