首先离散化颜色

设pre[x]表示与x颜色相同的点上一次出现的位置，对于每种颜色开一个set维护

修改时需要修改x、x修改前的后继、x修改后的后继

询问[l,r]等价于询问[l,r]内pre[x]<l的点的权值和

线段树套Treap维护

 

#include
     
      #include
      
       #include
       
        #include
        
         #define N 100010using namespace std;typedef long long ll;int n,m,i,x,y,pre,nxt,a[N],b[N<<1],C,que[N][3],loc[N<<1];char ch;ll ans;set
         
          T[N<<1];set
          
           ::iterator j,k;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline int lower(int x){ int l=1,r=C,t,mid; while(l<=r)if(b[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1; return t;}struct node{ int val,p;ll v,sum;node*l,*r; node(){val=v=sum=p=0;l=r=NULL;} inline void up(){sum=v+l->sum+r->sum;}}*blank=new(node),*root[N<<2];inline void Rotatel(node*&x){node*y=x->r;x->r=y->l;x->up();y->l=x;y->up();x=y;}inline void Rotater(node*&x){node*y=x->l;x->l=y->r;x->up();y->r=x;y->up();x=y;}void Ins(node*&x,int p,int v){ if(x==blank){ x=new(node);x->val=p;x->l=x->r=blank;x->v=x->sum=v;x->p=std::rand(); return; } x->sum+=v; if(p==x->val){x->v+=v;return;} if(p
           
            val){ Ins(x->l,p,v); if(x->l->p>x->p)Rotater(x); }else{ Ins(x->r,p,v); if(x->r->p>x->p)Rotatel(x); }}ll Ask(node*x,int p){ if(x==blank)return 0; if(p==x->val)return x->l->sum; if(p>x->val)return x->v+x->l->sum+Ask(x->r,p); return Ask(x->l,p);}void build(int x,int a,int b){ root[x]=blank; if(a==b)return; int mid=(a+b)>>1; build(x<<1,a,mid),build(x<<1|1,mid+1,b);}inline void add(int c,int d,int e){ int x=1,a=1,b=n,mid; while(a
            
             >1;x<<=1; if(c<=mid)b=mid;else a=mid+1,x|=1; } Ins(root[x],d,e);}void ask(int x,int a,int b,int c,int d,int e){ if(c<=a&&b<=d){ans+=Ask(root[x],e);return;} int mid=(a+b)>>1; if(c<=mid)ask(x<<1,a,mid,c,d,e); if(d>mid)ask(x<<1|1,mid+1,b,c,d,e);}int main(){ blank->l=blank->r=blank; for(read(n),i=1;i<=n;i++)read(a[i]),b[++C]=a[i]; for(read(m),i=1;i<=m;i++){ while(!(((ch=getchar())=='U')||(ch=='Q'))); read(que[i][1]),read(que[i][2]); if(ch=='U')b[++C]=que[i][2];else que[i][0]=1; } for(sort(b+1,b+C+1),i=1;i<=C;i++)T[i].insert(0),T[i].insert(n+1); for(build(i=1,1,n);i<=n;i++){ T[a[i]=lower(a[i])].insert(i); add(i,loc[a[i]],b[a[i]]); loc[a[i]]=i; } for(i=1;i<=m;i++)if(que[i][0])ans=0,ask(1,1,n,que[i][1],que[i][2],que[i][1]),printf("%lld\n",ans); else{ x=que[i][1],y=lower(que[i][2]); k=j=T[a[x]].find(x);k--;pre=*k;k=j;k++;nxt=*k; add(x,pre,-b[a[x]]); if(nxt<=n)add(nxt,x,-b[a[x]]),add(nxt,pre,b[a[x]]); T[a[x]].erase(x); T[a[x]=y].insert(x); k=j=T[y].find(x);k--;pre=*k;k=j;k++;nxt=*k; add(x,pre,b[y]); if(nxt<=n)add(nxt,pre,-b[y]),add(nxt,x,b[y]); } return 0;}