别碰我！

自己还是太蒟了……

看了好久，最后抄参考题解打出来的……

前面的可能影响后面的，所以按照询问右端点排序

这时候维护一个前缀和数组就可以了，

那么问题又来了，去重？

可以这样，从前往后枚举，如果被加过了就在前面去掉

具体看代码（题目毒瘤导致卡常卡了好几遍）：

 #include<bits/stdc++.h>

 #define rint register int

 #define lowbit(x) (x&(-x))

 using namespace std;

 int n,m,t[],a[],vis[],ot[];

 inline int rd(){

     int x=,f=;

     char c=getchar();

     while(c<''||c>''){

         if(c=='-')f=-;

         c=getchar();

     }

     while(c>=''&&c<=''){

         x=x*+c-'';

         c=getchar();

     }

     return x*f;

 }

 struct Question {

     int l,r,id;

 }q[];

 inline bool cmp(Question a,Question b){

     return a.r<b.r;

 }

 inline void AddPoint(int x,int add){

     while(x<=n){

         t[x]+=add;

         x+=lowbit(x);

     }

 }

 inline int Sum(int x){

     int ans=;

     while(x){

         ans+=t[x];

         x-=lowbit(x);

     }

     return ans;

 }

 inline int QuerySec(int l,int r){

     return Sum(r)-Sum(l-);

 }

 int main(){

     n=rd();

     for(rint i=;i<=n;i++)a[i]=rd();

     cin>>m;

     for(rint i=;i<=m;i++){

         q[i].l=rd();

         q[i].r=rd();

         q[i].id=i;

     }

     sort(q+,q++m,cmp);

     int now=;

     for(rint i=;i<=m;i++){

         for(rint j=now;j<=q[i].r;j++){

             if(vis[a[j]]){//如果加过了

                 AddPoint(vis[a[j]],-);//去掉

             }

             AddPoint(j,);//新加上的

             vis[a[j]]=j;//标记

         }

         now=q[i].r+;

         ot[q[i].id]=QuerySec(q[i].l,q[i].r);//注意顺序

     }

     for(rint i=;i<=m;i++)cout<<ot[i]<<endl;

     return ;

 }

因为是离线枚举所以千万不要忘了存回去！

[洛谷P1972][题解][SDOI2009]HH的项链的相关教程结束。