我知道这是很典的题，但是看提交记录发现我是今年 1 月做的，居然一点印象也没有。
看题解（洛谷第一篇）居然看懂了，比较开心。之前都是随便看看然后就开始贺题解，感觉思考的比较少，这次是看着推导过程写出来了。
思路：对于询问多个区间 [L,R] 中出现不同数字个数，当 R 相同时，如果区间出现了重复数字，那么我们只需要关心最右端的这个数字就可以了。换言之，重复出现的数字在左端将无任何贡献。例如 1 2 3 1 4，在询问 [1,4] 时，第一个 1 无任何贡献，并且当询问的 R 不断右移的过程中，第一个 1 都无任何意义，被第四位置的替代掉。
于是把询问离线下来，按照询问的右端点排序。
当出现一个数字时，如果这个数字曾经出现，则 insert(lst[pos[i]],-1)，把这个数在上一个位置的标记清掉，insert(pos[i],1) 来更新这个数字的新位置。
用树状数组单点修改、区间查询，常数、空间都较小。用前缀和 query(R)-query(L-1) 把这一段的数字数出来。
#include<bits/stdc++.h>
const int N=1e6+10;
using namespace std;
int n,Q;
int a[N],t[N];
int lst[N],ans[N];
struct node{int L,R,id;}q[N];
bool cmp(node x,node y){
return x.R<y.R;
}
int lowbit(int x){
return x&(-x);
}
void insert(int x,int v){
while(x<=n){
t[x]+=v;
x+=lowbit(x);
}
}
int query(int x){
int res=0;
while(x){
res+=t[x];
x-=lowbit(x);
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&Q);
for(int i=1;i<=Q;i++){
scanf("%d%d",&q[i].L,&q[i].R);
q[i].id=i;
}
sort(q+1,q+Q+1,cmp);
for(int i=1,top=1;i<=n;i++){
if(lst[a[i]]) insert(lst[a[i]],-1);
insert(i,1);
lst[a[i]]=i;
while(top<=Q&&q[top].R==i){
ans[q[top].id]=query(q[top].R)-query(q[top].L-1);
top++;
}
}
for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
return 0;
}