自己还是太蒟了……
看了好久，最后抄参考题解打出来的……
前面的可能影响后面的，所以按照询问右端点排序
这时候维护一个前缀和数组就可以了，
那么问题又来了，去重？
可以这样，从前往后枚举，如果被加过了就在前面去掉
具体看代码（题目毒瘤导致卡常卡了好几遍）：
1 #include<bits/stdc++.h>
2 #define rint register int
3 #define lowbit(x) (x&(-x))
4 using namespace std;
5 int n,m,t[1000010],a[1000010],vis[1000010],ot[1000010];
6 inline int rd(){
7 int x=0,f=1;
8 char c=getchar();
9 while(c<'0'||c>'9'){
10 if(c=='-')f=-1;
11 c=getchar();
12 }
13 while(c>='0'&&c<='9'){
14 x=x*10+c-'0';
15 c=getchar();
16 }
17 return x*f;
18 }
19 struct Question {
20 int l,r,id;
21 }q[1000010];
22 inline bool cmp(Question a,Question b){
23 return a.r<b.r;
24 }
25 inline void AddPoint(int x,int add){
26 while(x<=n){
27 t[x]+=add;
28 x+=lowbit(x);
29 }
30 }
31 inline int Sum(int x){
32 int ans=0;
33 while(x){
34 ans+=t[x];
35 x-=lowbit(x);
36 }
37 return ans;
38 }
39 inline int QuerySec(int l,int r){
40 return Sum(r)-Sum(l-1);
41 }
42 int main(){
43 n=rd();
44 for(rint i=1;i<=n;i++)a[i]=rd();
45 cin>>m;
46 for(rint i=1;i<=m;i++){
47 q[i].l=rd();
48 q[i].r=rd();
49 q[i].id=i;
50 }
51 sort(q+1,q+1+m,cmp);
52 int now=1;
53 for(rint i=1;i<=m;i++){
54 for(rint j=now;j<=q[i].r;j++){
55 if(vis[a[j]]){//如果加过了
56 AddPoint(vis[a[j]],-1);//去掉
57 }
58 AddPoint(j,1);//新加上的
59 vis[a[j]]=j;//标记
60 }
61 now=q[i].r+1;
62 ot[q[i].id]=QuerySec(q[i].l,q[i].r);//注意顺序
63 }
64 for(rint i=1;i<=m;i++)cout<<ot[i]<<endl;
65 return 0;
66 }
因为是离线枚举所以千万不要忘了存回去！