题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。
有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入格式
一行一个正整数 nn，表示项链长度。
第二行 nn 个正整数 aia**i，表示项链中第 ii 个贝壳的种类。
第三行一个整数 mm，表示 HH 询问的个数。
接下来 mm 行，每行两个整数 l,rl,r，表示询问的区间。
输出格式
输出 mm 行，每行一个整数，依次表示询问对应的答案。
输入输出样例
输入 #1复制
6
1 2 3 4 3 5
3
1 2
3 5
2 6
输出 #1复制
2
2
4
这个题可以从 [l, r]的答案能够 O(1)扩展到 [l − 1, r], [l + 1, r], [l, r + 1], [l, r − 1]的答案，因此可以用莫队写。可惜的是数据卡掉了莫队，只能用树状数组、线段树等。
#include <bits/stdc++.h>
using namespace std;
int n, a[10000005], m, ans[10000005], block;
inline int read() {
char x;
while((x = getchar()) > '9' || x < '0') ;
int u = x - '0';
while((x = getchar()) <= '9' && x >= '0') u = (u << 3) + (u << 1) + x - '0';
return u;
}
int buf[105];
inline void write(int i) {
int p = 0;
if(i == 0) p++;
else while(i) {
buf[p++] = i % 10;
i /= 10;
}
for(int j = p-1; j >= 0; j--) putchar('0' + buf[j]);
}
struct node {
int l, r, id;
} q[10000005];
bool cmp(node a, node b) {
return (a.l / block) ^ (b.l / block)? (a.l / block) < (b.l / block) : (a.l / block) & 1? a.r < b.r: a.r > b.r;
}
int Ans = 0, cnt[10000001];
void add(int x) {
if(!cnt[a[x]]) Ans++;
cnt[a[x]]++;
}
void del(int x) {
cnt[a[x]]--;
if(!cnt[a[x]]) Ans--;
}
int main() {
n = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
}
m = read();
block = n / sqrt(m * 2 / 3);
for (int i = 1; i <= m; i++) {
q[i].l = read(); q[i].r = read(); q[i].id = i;
}
sort(q + 1, q + m + 1, cmp);
int l = 0, r = 0;
for(int i = 1; i <= m; i++) {
int ql = q[i].l, qr = q[i].r;
while(l < ql) del(l++);
while(l > ql) add(--l);
while(r < qr) add(++r);
while(r > qr) del(r--);
ans[q[i].id] = Ans;
}
for(int i = 1; i <= m; i++) {
write(ans[i]); putchar('
');
}
return 0;
}