带修改莫队，每次查询前调整修改

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define N 20005using namespace std;int n,m,nn,a[N],be[N],l,r,num[1000005],tot,qq,cc;bool vis[N];struct Change{	int pos,nxt,pre;}ch[1005];struct Query{	int l,r,tim,id,ans;}qr[10005];bool cmp1(Query a,Query b){	if(be[a.l]==be[b.l]) return a.r
         
          =l&&pos<=r){ if(!(--num[a[pos]])) tot--; if(++num[now]==1) tot++; } a[pos]=now;}void update(int pos){ if(vis[pos]){ vis[pos]=0; if(!(--num[a[pos]])) tot--; return ; } if(!vis[pos]){ vis[pos]=1; if(++num[a[pos]]==1) tot++; return ; }}void work(){ l=1,r=0,tot=0; qr[0].tim=cc; for(int i=1;i<=qq;i++){ //printf("%d %d %d %d\n",qr[i].l,qr[i].r,qr[i].id,qr[i].tim); for(int j=qr[i-1].tim+1;j<=qr[i].tim;j++) change(ch[j].pos,ch[j].nxt); for(int j=qr[i-1].tim;j>qr[i].tim;j--) change(ch[j].pos,ch[j].pre); while(l
          
           qr[i].l) update(--l); while(r
           
            qr[i].r) update(r--); qr[i].ans=tot; }}int main(){ scanf("%d%d",&n,&m); nn=(int)sqrt(n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); be[i]=(i-1)/nn+1; } char s; int aa,bb; for(int i=1;i<=m;i++) { s=getchar(); while(s!='Q'&&s!='R')s=getchar(); scanf("%d%d",&aa,&bb); if(s=='R'){ ch[++cc].pos=aa; ch[cc].nxt=bb; ch[cc].pre=a[aa]; a[aa]=bb; } if(s=='Q'){ qr[++qq].tim=cc; qr[qq].l=aa; qr[qq].r=bb; qr[qq].id=qq; } } sort(qr+1,qr+qq+1,cmp1); work(); sort(qr+1,qr+qq+1,cmp2); for(int i=1;i<=qq;i++) printf("%d\n",qr[i].ans); return 0;}