http://www.zybbs.org/JudgeOnline/problem.php?id=2120

10000个数，10000个操作。每次修改一个数/询问一段区间内不同的数有几个。

有点难想……树状数组线段树套平衡树。每个数第一次出现时随便改成一个负数（我改成了这个数的相反数以避免重值），之后改成前一次出现的位置。询问的时候查找一个区间中比左端点小的数有几个（就是没有前继/是区间中第一次出现的数的个数）。

然后这个可以用平衡树维护。由于询问是对于区间的，所以用树状数组线段树套上……

将点i的颜色修改为j的时候要修改i的后继，颜色j对于i的后继和i本身，这里还要用个平衡树维护每个颜色的位置……对于前/后继不存在的情况还要特判……超麻烦……

我的程序又慢又长……不过好歹是第一个树套树的程序……做个纪念！

Update:改成了树状数组……然后Find的时候如果相等就直接返回……瞬间快了……

但是tim大神SegTree+Splay600+MS！！太神了！！不过18K+的代码长度……

至于长度嘛……为什么2K+的代码会被你们写成6K+……

NZM大神说XXXXXXXX必须离线BIT套BIT乱搞……但是我先去试试我的SB方法……

#include <stdio.h>
typedef struct _Splay{struct _Splay *c[2],*f;int s,v;}Splay,*PSplay;
Splay null,st[16][10000],*a[10001],*c[1000000];
char str[300000],*p=str;
int n,k[1000000],b[10000];
inline PSplay updt(PSplay x){return x->s=x->c[0]->s+x->c[1]->s+1,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;x->s=1;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;for(;r!=&null;r=r->c[r->v<x])if(r->v==x)return splay(r,&null);else if(r->v>x&&(ans==&null||r->v<ans->v))ans=r;
	return splay(ans,&null);
}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 BitQuery(i,y){int ans=0;PSplay x;for(;i;i-=i&-i)ans+=(x=Find(a[i],y))==&null?a[i]->s:(a[i]=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;PSplay x;fread(p,1,300000,stdin);
	null.f=null.c[0]=null.c[1]=&null;n=getint();
	for(t=getint();++i!=n;k[b[i]]=i+1){
		BitInsert(i+1,k[b[i]=getint()-1]?k[b[i]]:-b[i]);
		c[b[i]]=Insert(c[b[i]],node(st[15]+i,i+1));
	}while(t--)if(*++p=='Q')printf("%d\n",BitQuery(getint(),i=getint())-BitQuery(i-1,i));
	else if(*p=='R'){
		if(b[i=getint()-1]==(j=getint()-1))continue;
		if(!c[j])c[j]=&null;c[b[i]]=Remove(st[15]+i);
		if((x=near(st[15]+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((c[j]=x)->v,i+1),BitUpdate(i+1,c[j]->c[0]==&null?-j:near(c[j],0)->v);
		c[b[i]=j]=Insert(c[j],node(st[15]+i,i+1));
	}else t++;return 0;
}

• inline
• block