题目描述
HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入格式
第一行：一个整数N，表示项链的长度。
第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。
第三行：一个整数M，表示HH询问的个数。
接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式
M行，每行一个整数，依次表示询问对应的答案。
样例
样例输入
6
1 2 3 4 3 5
3
1 2
3 5
2 6
样例输出
2
2
4
数据范围与提示 N ≤ 50000，M ≤ 200000
- 这道题要注意使用离线思想（将所有数据全部读入后统一处理）
- 定义树状数组只有“0”“1”两个状态表示是否出现
- 记录上一个和当前物品种类相同的物品在哪里，假如我们统计了当前物品，就把上一个相同种类的物品置 0.
- 记录每个区间的右端点，并从小到大排序.
- 取出一个最小的右端点，若当前对物品的遍历到达了这个右端点，那么马上算出答案并存储.
- 重复上述步骤.
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1000001;
int n, m, l, r, a[N], s[N], ans[N], vis[N];
struct tree{
int l, r, sum;
bool operator < (const tree &a) const{
return r < a.r;
}
}t[N];
int lb(int x){
return x & -x;
}
void add(int x, int key){
while(x <= n){
s[x] += key;
x += lb(x);
}
}
int gt(int x){
int sum = 0;
while(x){
sum += s[x];
x -= lb(x);
}
return sum;
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for(int i=1; i<=m; i++){
scanf("%d%d", &t[i].l, &t[i].r);
t[i].sum = i;
}
sort(t+1, t+1+m);
int last = 1;//上次结尾
for(int i=1; i<=m; i++){
for(int j=last; j<=t[i].r; j++){
if(vis[a[j]]) add(vis[a[j]], -1);//vis数组为一则之前出现过
add(j, 1);//为0则之前未出现过
vis[a[j]] = j;
}
last = t[i].r + 1;
ans[t[i].sum] = gt(t[i].r) - gt(t[i].l - 1);
}
for(int i=1; i<=m; i++) printf("%d\n", ans[i]);
return 0;
}