4028卡时苟过。。莫队·暴力大法好

补习了一发莫队其实很简单，但是之前忘了555

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,m,a[1010000];int st[1010000],block;struct node{ int l,r,x; int id;}q[2100000];bool cmp(node n1,node n2){ if(st[n1.l]
           
            
             1)ans-=c[a[x]]-1; c[a[x]]+=d; if(c[a[x]]>1)ans+=c[a[x]]-1;}void solve(){ int l=1,r=0;ans=0; for(int i=1;i<=m;i++) { while(l
             
              q[i].l)change(l-1,1),l--; while(r
              
               q[i].r)change(r,-1),r--; q[i].x=q[i].r-q[i].l+1-ans; }}int main(){ scanf("%d",&n);block=sqrt(n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),st[i]=(i-1)/block+1; scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i; sort(q+1,q+m+1,cmp); solve(); sort(q+1,q+m+1,cmd); for(int i=1;i<=m;i++)printf("%d\n",q[i].x); return 0;}