BZOJ2120: 数颜色

---

题目描述

题目分析

带修莫队的模板题。

带修莫队时间复杂度看上去很高的样子。。。

是代码呢

#include 
    
     using namespace std;const int MAXN=1e5+7;struct Q{    int l,r,time,id,ans;    inline bool operator <(const Q &rhs)const{return id
     
      '9')&&ch!='-')ch=getchar();    while(ch=='-')c*=-1,ch=getchar();    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();    return x*c;}int main(){    n=read();m=read();    int S=pow(n,0.66666666);    for(int i=1;i<=n;i++) now[i]=s[i]=read(),belong[i]=(i-1)/S+1;    for(int i=1;i<=m;i++) {        scanf("%s",opt);        int x=read(),y=read();        if(opt[0]=='Q') q[++t]=(Q){x,y,T,t};        else c[++T]=(C){x,y,now[x]},now[x]=y;    }    sort(q+1,q+t+1,cmp);    for(int i=1;i<=t;i++){        while(Time
      
       q[i].time) change(c[Time].pos,c[Time].old),Time--;        while(l
       
        q[i].l) add(s[l-1]),l--;        while(r
        
         q[i].r) del(s[r]),r--;        q[i].ans=ans;    }    sort(q+1,q+t+1);    for(int i=1;i<=t;i++) printf("%d\n",q[i].ans);}