bzoj3678: wangxz与OJ Splay缩点

#include<bits/stdc++.h>
#define L(t) (t)->c[0]
#define R(t) (t)->c[1]
#define F(t) (L(t)->s+1)
#define G(t) (L(t)->s+(t)->u)
#define M (l+r>>1)
struct node{
	int v,s,u;
	node* c[2];
	node(int v,int s,int u,node* a,node* e)
	:v(v),s(s),u(u){
		c[0]=a,c[1]=e;
	}
}*null=new node(0,0,0,0,0),*root=0;
node* update(node* t){
	t->s=G(t)+R(t)->s;
	return t;
}
void link(bool i,node*& t,node*& s){
	node* d=t->c[i];
	t->c[i]=s;
	s=update(t);
	t=d;
}
void splay(int v,node*& t=root){
	node* d[]={null,null};
	while(1){
		if(F(t)<=v&&v<=G(t)){
			if(t->u!=1)
				t=new node(t->v+v-F(t),
				t->s,1,v==F(t)?L(t)
				:new node(t->v,v-1,v-F(t),
				L(t),null),v==G(t)?R(t)
				:new node(t->v+v-F(t)+1,
				t->s-v,G(t)-v,null,R(t)));
			break;
		}
		bool i=v>G(t);
		v-=i*G(t);
		if(!(F(t->c[i])<=v&&v<=G(t->c[i]))
		&&i==v>G(t->c[i])){
			v-=i*G(t->c[i]);
			link(i,t,t->c[i]->c[i^1]);
		}
		link(i,t,d[i]);
	}
	for(int i=0;i!=2;++i){
		node* s=t->c[i^1];
		while(d[i]!=null)
			link(i,d[i],s);
		t->c[i^1]=s;
	}
	update(t);
}
node* build(int* v,int l,int r){
	return l>r?null
	:new node(v[M],r-l+1,1,
	build(v,l,M-1),
	build(v,M+1,r));
}
node*& interval(int l,int r){
	splay(l);
	splay(r-l+2,R(root));
	return L(R(root));
}
int v[20010];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d",v+i);
	root=build(v,0,n+1);
	while(m--){
		int s,t,a,b;
		scanf("%d%d",&s,&t);
		switch(s){
		case 0:
			scanf("%d%d",&a,&b);
			interval(t+1,t)=new node(
			a,b-a+1,b-a+1,null,null);
			break;
		case 1:
			scanf("%d",&a);
			interval(t,a)=null;
			break;
		case 2:
			splay(t+1);
			printf("%d\n",root->v);
			break;
		}
	}
}