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

做了两个多小时，被傻逼错误各种屠，最搞笑的是我没下传标记拍了几组N,M=10000的随机数据都是对的。。。

这题的标准解法是离线算法。。就是先全部U起来，然后处理出DFS序就可以发现每次操作的都是一段区间。。。线段树乱搞就可以了。。好像挺好写的。。。

但是像我这么弱的只能写写在线算法。。其中F3只要全局维护一个堆就行了，A3只要搞个全局变量表示所有数加了多少，那么剩下的东西，由于要合并两堆+取最大值，自然而然想到了可并堆。。。要打标记表示某个点的子树加了多少。。。

可并堆我只会左偏树，但当左链很长的时候好像会囧掉（而且还要支持减小一个数！）。。。于是我选用了随机堆。。。就是合并的时候随机一个儿子合并，这样可以让堆的高度期望在logN级。。那就可以在logN时间内Sink/Swim/将一个点及其祖先们的标记全部下传了。。。

嘛。。。随机的话按照左右左右左右。。。这么随也很快。。。

表示长期不写Splay现在连个rotate操作都写了30+分钟。。。我真是弱暴了。。。

随机数据比Tim快很多。。。看来这个数据还是下了点心思的，说不定就卡掉了左偏树。。。很久以前我写过启发式合并TLE了（不过我不排除我写的程序会死循环的可能）。。。当然如果神犇们要虐配对堆/F-Heap的话说不定也行（二项堆貌似不行）。。。我反正不会。。。

#include<stdio.h>
#define H struct Heap
#define updt(x) a[x]=a[x<<1]>a[x<<1^1]?a[x<<1]:a[x<<1^1]
H{H*c[2],*f;int v,a}T[300000],*S[300000];
inline H*tran(H*x){if(x->a){x->v+=x->a;if(x->c[0])x->c[0]->a+=x->a;if(x->c[1])x->c[1]->a+=x->a;x->a=0;}return x;}
int n,d,s,f[300000],a[1048576],M;_Bool C;
char str[10000000],*p=str,*o=str;
inline void UPDT(x){for(x+=M;x>>=1;)updt(x);}
inline find(x){
	int y=f[x],r=y;
	while(r!=f[r])r=f[r];
	while((f[x]=r)!=(x=y))y=f[y];
	return r;
}H*Merge(H*x,H*y){
	H*t;_Bool c;if(!y)return x;if(!x)return y;
	tran(x);tran(y);
	if(x->v<y->v)t=x,x=y,y=t;
	c=C;C=!C;return(x->c[c]=Merge(x->c[c],y))->f=x;
}inline H*Root(H*x){s=0;while(x)S[s++]=x,x=x->f;return S[s-1];}
inline void rot(H*x){
	H*t=x->f,*x0,*x1;_Bool c=t->c[1]==x;
	if(t->f)t->f->c[t->f->c[1]==t]=x;
	if(x0=x->c[0])x->c[0]->f=t;if(x1=x->c[1])x->c[1]->f=t;
	x->f=t->f;(t->f=x)->c[c]=t;if(x->c[!c]=t->c[!c])x->c[!c]->f=x;
	t->c[0]=x0;t->c[1]=x1;
}inline H*Swim(H*x){while(x->f)if(tran(x->f)->v<tran(x)->v)rot(x);else return x;return x;}
inline void Sink(H*x){
	while(1){
		if(tran(x)->c[0])tran(x->c[0]);if(x->c[1])tran(x->c[1]);
		if(!x->c[0]||x->c[0]->v<=x->v){
			if(!x->c[1]||x->c[1]->v<=x->v)return;
			else rot(x->c[1]);
		}else if(!x->c[1]||x->c[1]->v<=x->v)rot(x->c[0]);
		else rot(x->c[x->c[1]->v>x->c[0]->v]);
	}
}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;
}inline void print(x){
	char buf[10],*p=buf;
	if(x<0)x=-x,*o++='-';if(!x)*o++=48;
	else{while(x)*p++=x%10+48,x/=10;while(p--!=buf)*o++=*p;}
	*o++='\n';
}main(){
	int i=-1,j,q;H*x0,*x1;fread(p,1,10000000,stdin);
	for(M=1<<32-__builtin_clz((n=getint())-1);++i!=n;)T[f[i]=i].v=a[M+i]=getint();
	for(i--;++i!=M;)a[M+i]=1<<31;while(--i)updt(i);
	for(q=getint();q--;){
		while(*p!='A'&&*p!='U'&&*p!='F')p++;
		if(*p=='A'){
			if(*++p=='1'){
				p++;i=getint()-1;T[i].v+=j=getint();
				if(j<0){
					if(T[i].f)x0=x1=0;else x0=T[i].c[0],x1=T[i].c[1];
					Sink(T+i);
					if(!T[i].f)a[M+find(i)]=T[i].v,UPDT(f[i]);
					else if(x0&&!x0->f)a[M+find(i)]=x0->v,UPDT(f[i]);
					else if(x1&&!x1->f)a[M+find(i)]=x1->v,UPDT(f[i]);
				}else if(j&&!Swim(T+i)->f)a[M+find(i)]=T[i].v,UPDT(f[i]);
			}else if(*p++=='2')i=getint()-1,Root(T+i)->a+=getint(),a[M+find(i)]=tran(S[s-1])->v,UPDT(f[i]);
			else d+=getint();
		}else if(*p=='F'){
			if(*++p=='1'){
				p++;Root(T+(i=getint()-1));
				while(s--)tran(S[s]);print(T[i].v+d);
			}else if(*p++=='2')print(tran(Root(T+getint()-1))->v+d);
			else print(a[1]+d);
		}else if((i=find(getint()-1))!=(j=find(getint()-1))){
			if(a[M+i]<a[M+j])i^=j^=i^=j;
			f[j]=i,Merge(Root(T+i),Root(T+j)),a[M+j]=1<<31,UPDT(j);
		}
	}return fwrite(str,1,o-str,stdout),0;
}

• inline
• block