http://www.spoj.pl/problems/XXXXXXXX/

PS：BZOJ太奥交了，囧视之！

做了数颜色以后这题就变成水题了……就是离散化麻烦点……现在写的是排序+二分的……如果有时间就改成hash的……找了半天hash函数，最快的那个比二分还慢……55555

NZM教我这题应该树状数组套树状数组，然后想半天（真的半天！）没想明白……只好写NZM说会TLE的树状数组套平衡树……于是A了囧……不过只有rank10……

具体做法和数颜色一模一样，只是size域的维护中，一个点的值由1改为这个点的数值……

这个时候C的劣势就体现出来了……（虽然我承认可以用奇葩的函数指针，但是我讨厌那种写法）就是两个平衡树维护的东西不一样……如果不想写两个平衡树的话……就会有点烦……

不过个人认为离散化更烦……调的我飞了起来！唉唉说到底还是我离散化的题做的太少了啊……

然后对拍的时候一直段错误最后发现原来数颜色中修改是R这题是U……晕倒……

#include <stdio.h>
#include <stdlib.h>
typedef struct _Splay{struct _Splay *c[2],*f;long long s;int v;}Splay,*PSplay;
Splay null,st[18][50000],*a[50001],*c[150001];
char str[3000000],*p=str;
int n,k[150001],b[50000],num[150001],sn=-1;
struct inst{_Bool p;int i,j;}ins[100000];
inline PSplay updt(PSplay x){if(x<st[17])x->s=x->c[0]->s+x->c[1]->s+num[b[(x-*st)%50000]];return x;}
inline PSplay near(PSplay x,_Bool c){for(x=x->c[c];x->c[!c]!=&null;x=x->c[!c]);return x;}
inline PSplay extr(PSplay x,_Bool c){while(x->c[c]!=&null)x=x->c[c];return x;}
inline PSplay node(PSplay x,int v){x->f=x->c[0]=x->c[1]=&null;x->v=v;if(x<st[17])x->s=num[b[(x-*st)%50000]];return x;}
inline PSplay rot(PSplay x){
	PSplay fx=x->f,ffx=fx->f;
	_Bool c=fx->c[1]==x,fc=ffx->c[1]==fx;
	if(fx!=&null){
		if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx;
		if((x->f=ffx)!=&null)ffx->c[fc]=x;
		updt((fx->f=x)->c[!c]=fx);
	}return x;
}inline PSplay splay(PSplay x,PSplay p){
	if(x==&null)return x;for(;x->f!=p;rot(x))if(x->f->f!=p)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x);
	return updt(x);
}inline PSplay Join(PSplay x,PSplay y){
	if(x==&null)return y;if(y==&null)return x;x=splay(extr(x,1),&null);
	return updt((x->c[1]=splay(y,&null))->f=x);
}inline PSplay Remove(PSplay x){x=splay(x,&null);x->c[0]->f=x->c[1]->f=&null;return Join(x->c[0],x->c[1]);}
inline PSplay Insert(PSplay r,PSplay x){
	_Bool c;if(!r||r==&null)return x;
	while(r->c[c=r->v<x->v]!=&null)r=r->c[c];
	(r->c[c]=x)->f=r;return splay(x,&null);
}inline PSplay Find(PSplay *r,int x){
	PSplay ans=&null,t=&null;
	for(;*r!=&null;*r=t->c[t->v<x])if((t=*r)->v==x)return *r=splay(t,&null);else if(t->v>x&&(ans==&null||t->v<ans->v))ans=t;
	*r=splay(ans==&null?t:ans,&null);return ans;
}cmp(const void *a,const void *b){return *(int*)a-*(int*)b;}
inline find(x){int l=0,r=sn,mid;for(;;num[mid]>x?(r=mid):(l=mid))if(num[mid=l+r>>1]==x)return mid;}
inline void BitInsert(i,x){int y=0,s=i-1;for(;i<=n;i+=i&-i)a[i]=Insert(a[i],node(st[y++]+s,x));}
inline void BitUpdate(i,x){int y=0,s=i-1;for(;i<=n;i+=i&-i)a[i]=Remove(st[y]+s),a[i]=Insert(a[i],node(st[y++]+s,x));}
inline long long BitQuery(i,y){long long ans=0;PSplay x;for(;i;i-=i&-i)ans+=(x=Find(a+i,y))==&null?a[i]->s:x->c[0]->s;return ans;}
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}main(){
	int i=-1,j=0,t,kk=-1;PSplay x;fread(p,1,3000000,stdin);
	null.f=null.c[0]=null.c[1]=&null;
	for(n=getint();++sn!=n;)num[sn]=b[sn]=getint();
	for(t=getint();++kk!=t;){
		while(*++p!='U'&&*p!='Q');
		if(ins[kk].p=*p=='U')ins[kk].i=getint(),ins[kk].j=num[sn++]=getint();
		else ins[kk].i=getint(),ins[kk].j=getint();
	}for(qsort(num,sn,4,cmp),kk=1;++j!=sn;)if(num[j]!=num[j-1])num[kk++]=num[j];sn=kk;
	for(kk=-1;++i!=n;k[b[i]]=i+1){
		BitInsert(i+1,k[b[i]=find(b[i])]?k[b[i]]:-b[i]);
		c[b[i]]=Insert(c[b[i]],node(st[17]+i,i+1));
	}while(++kk!=t)if(ins[kk].p){
		if(num[b[i=ins[kk].i-1]]==(j=ins[kk].j))continue;
		c[b[i]]=Remove(st[17]+i);if(!c[b[i]=j=find(j)])c[j]=&null;
		if((x=near(st[17]+i,1))!=&null)BitUpdate(x->v,st[0][i].v);
		if((x=Find(c+j,i+1))==&null)BitUpdate(i+1,c[j]==&null?-j:(c[j]=splay(extr(c[j],1),&null))->v);
		else BitUpdate(x->v,i+1),BitUpdate(i+1,x->c[0]==&null?-j:(c[j]=splay(near(x,0),&null))->v);
		c[j]=Insert(c[j],node(st[17]+i,i+1));
	}else printf("%lld\n",BitQuery(ins[kk].j,ins[kk].i)-BitQuery(ins[kk].i-1,ins[kk].i));
	return 0;
}

• inline
• block