自己还是太蒟了……
看了好久，最后抄参考题解打出来的……
前面的可能影响后面的，所以按照询问右端点排序
这时候维护一个前缀和数组就可以了，
那么问题又来了，去重？
可以这样，从前往后枚举，如果被加过了就在前面去掉
具体看代码（题目毒瘤导致卡常卡了好几遍）：
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 }