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

1A有木有！超开心……

某日看到fotile主席用4种方法在虐这题，深深被震撼，再次Orz！最神的一种方法是主席自己create的SBT进化版——主席树！主席说主席树可以秒杀一切神题！！！Orz！！！

这个是我A掉的第一个有一堆卫星数据的Splay题……留个念吧……

我对这种题木的唯一感觉就是Splay……空节点的特判我用null.l=null.r=-100000trick掉了，但是没敢插入头尾节点……所以在移动到第一个数前/最后一个数后的时候进行特判了囧……

Q的时候切掉1..i-1,j+1..s，update后输出整棵树的max就可以了……最后再将1..i-1接到最左边，j+1..s接到最右边……虽然这样有点慢但是我想不出更好的方法了T^T

彻底变傻X……可以splay第j个数，如果i=j则就是根的值，否则在左子树中splay第i个数，然后切掉它的左子树和根的右子树，update后再直接接回去……不过这样还是没tbl神犇快……改成C++就快了一点……不开O2其实还是C++快啊……

对一个节点（线段）记录lmax,rmax,max,sum。这四个用节点上的数推一下就可以了，很简单的……

注意改好后对修改的节点update啊……

另外没什么好说的……代码超长……70行TAT

#include <stdio.h>
#include <string.h>
#define maxn 200000
#define max(a,b) ((a)>(b)?(a):(b))
typedef struct _Splay{struct _Splay *c[2],*f;int s,v,l,r,m,a;}Splay,*PSplay;
Splay null,st[maxn],*stp=st,*r=&null;
char str[3000000],*p=str;
inline PSplay update(PSplay x){
	int ml=max(x->c[1]->l,0),mr=max(x->c[0]->r,0);
	x->s=x->c[0]->s+x->c[1]->s+1;
	x->a=x->c[0]->a+x->v+x->c[1]->a;
	x->l=max(x->c[0]->l,x->c[0]->a+x->v+ml);
	x->r=max(x->c[1]->r,x->c[1]->a+x->v+mr);
	return x->m=max(max(x->c[0]->m,x->c[1]->m),ml+x->v+mr),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;
		update((fx->f=x)->c[!c]=fx);
	}return x;
}inline PSplay splay(PSplay x){
	if(x==&null||x->f==&null)return update(x);
	for(;x->f!=&null;rot(x))if(x->f->f!=&null)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x);
	return update(x);
}inline PSplay Join(PSplay r1,PSplay r2){
	if(r1==&null)return r2;if(r2==&null)return r1;
	while(r1->c[1]!=&null)r1=r1->c[1];
	return update((splay(r1)->c[1]=r2)->f=r1);
}inline PSplay Rank(PSplay r,int x){
	_Bool c;
	if(x<=0||r->s<x)return &null;
	for(;;r=r->c[c])if(x==r->c[0]->s+1)return splay(r);else if(c=x>r->c[0]->s)x-=r->c[0]->s+1;
}inline getint(){
	int re=0;_Bool k;
	while(*p!='-'&&(*p<'0'||*p>'9'))p++;
	for(k=*p=='-'&&++p;*p>='0'&&*p<='9';)re=re*10+*p++-48;
	return k?-re:re;
}main(){
	int i,j;PSplay t1,t2;fread(str,1,3000000,stdin);
	for((null.f=null.c[0]=null.c[1]=&null)->m=null.l=null.r=-1000000,i=getint();i--;stp->v=getint(),r=update(stp++))if((stp->c[0]=r)!=(stp->c[1]=&null))r->f=stp;r->f=&null;
	while(1){
		while(*++p<'A'||*p>'Z')if(!*p)return 0;
		if(*p=='Q'){
			i=getint();t2=(r=Rank(r,j=getint()))->c[1];
			if(i==j){printf("%d\n",r->v);continue;}
			r->c[1]=&null;
			if(i!=1){
				r->c[0]->f=&null;
				t1=(r->c[0]=Rank(r->c[0],i))->c[0];
				(r->c[0]->f=r)->c[0]->c[0]=&null;
				update(r->c[0]);
			}printf("%d\n",update(r)->m);
			if(i!=1)r->c[0]->c[0]=t1,update(r->c[0]);
			r->c[1]=t2;update(r);
		}else if(*p=='R')update(((r=Rank(r,getint()))->v=getint(),r));
		else if(*p=='D'){
			r=Rank(r,getint());
			r->c[0]->f=r->c[1]->f=&null;
			r=Join(r->c[0],r->c[1]);
		}else if(stp->c[0]=stp->c[1]=&null,i=getint(),stp->v=getint(),i==r->s+1){
			while(r->c[1]!=&null)r=r->c[1];
			r=splay((stp->f=r)->c[1]=stp++);
		}else{
			stp->c[0]=(stp->f=r=Rank(r,i))->c[0];
			update(r->c[0]=r->c[0]->f=stp++);update(r);
		}
	}
}

• inline
• block