【BZOJ3678】wangxz与OJ

  这题不能用rope...因为总的插入点数可能非常大，rope也不回收内存。

  Splay加缩点，每次要用到一个点时把点给拆开。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=200010;

struct Splay_Tree
{
	struct Node
	{
		Node *c[2],*p;
		int size;
		int l,r;
		int w() {return this==p->c[1];}
	}MEM[maxn],*Null,*root;
	int IDs;

	#define ls x->c[0]
	#define rs x->c[1]

	Node *NewNode(int l,int r)
	{
		if (l>r) return Null;
		Node *x=&MEM[++IDs];
		ls=rs=x->p=Null;
		x->l=l;
		x->r=r;
		x->size=r-l+1;
		return x;
	}

	Splay_Tree()
	{
		Null=&MEM[0];
		Null->c[0]=Null->c[1]=Null->p=Null;
		Null->size=0;
		Null->l=Null->r=0;
		Node *LeftNode=NewNode(0,0);
		Node *RightNode=NewNode(0,0);
		root=LeftNode;
		root->c[1]=RightNode;RightNode->p=root;root->size=2;
	}
	
	void Update(Node *x) {if (x==Null) return;x->size=ls->size+rs->size+(x->r-x->l+1);}

	void Rotate(Node *x)
	{
		Node *p=x->p;
		int w=x->w();
		if (p==root) root=x;
		x->p=p->p;p->p->c[p->w()]=x;
		x->c[!w]->p=p;p->c[w]=x->c[!w];
		x->c[!w]=p;p->p=x;
		Update(p);
	}

	void Splay(Node *x,Node *top)
	{
		if (x==Null) return;
		while (x->p!=top)
		{
			if (x->p->p==top) {Rotate(x);break;}
			if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
			else Rotate(x),Rotate(x);
		}
		Update(x);
	}

	Node* Prev(Node *x) {x=ls;while (rs!=Null) x=rs;return x;}
	Node* Next(Node *x) {x=rs;while (ls!=Null) x=ls;return x;}

	Node* Select(int k)
	{
		Node *x=root;
		while (k)
		{
			int lsz=ls->size,xsz=x->r-x->l+1;
			if (lsz>=k) x=ls;
			else if (lsz+xsz<k) k-=lsz+xsz,x=rs;
			else if (x->r==x->l) return x;
			else
			{
				int l=x->l,r=x->r,mid=l+(k-lsz)-1;
				Splay(x,Null);
				Splay(Prev(x),Null);
				Splay(Next(x),root);
				Node *Nd=NewNode(mid,mid),*Nl=NewNode(l,mid-1),*Nr=NewNode(mid+1,r);
				Nd->c[0]=Nl;Nl->p=Nd;
				Nd->c[1]=Nr;Nr->p=Nd;
				root->c[1]->c[0]=Nd;Nd->p=root->c[1];
				Splay(Nd,Null);
				return Nd;
			}
		}
	}

	Node *Build_Tree(int l,int r,int *a)
	{
		if (l>r) return Null;
		int mid=(l+r)>>1;
		Node *x=NewNode(a[mid],a[mid]);
		if (l==r) return x;
		ls=Build_Tree(l,mid-1,a);
		rs=Build_Tree(mid+1,r,a);
		ls->p=rs->p=x;
		Update(x);
		return x;
	}

	void Insert(int pos,int l,int r)
	{
		Node *x=NewNode(l,r);
		Node *ql=Select(pos+1),*qr=Select(pos+2);
		Splay(ql,Null);
		Splay(qr,root);
		root->c[1]->c[0]=x;x->p=root->c[1];
		Splay(x,Null);
	}

	void Insert(int pos,int *a,int n)
	{
		Node *x=Build_Tree(0,n-1,a);
		Node *ql=Select(pos+1),*qr=Select(pos+2);
		Splay(ql,Null);
		Splay(qr,root);
		root->c[1]->c[0]=x;x->p=root->c[1];
		Splay(x,Null);
	}

	void Delete(int l,int r)
	{
		Node *ql=Select(l),*qr=Select(r+2);
		Splay(ql,Null);
		Splay(qr,root);
		root->c[1]->c[0]=Null;
		Update(root->c[1]);Update(root);
	}

	int At(int x)
	{
		Splay(Select(x+1),Null);
		return root->l;
	}
}T;

int s[maxn];
int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++) scanf("%d",&s[i]);
	T.Insert(0,s,n);
	while (m--)
	{
		int sym,p,a,b;
		scanf("%d",&sym);
		if (sym==0)
		{
			scanf("%d%d%d",&p,&a,&b);
			T.Insert(p,a,b);
		}
		else if (sym==1) scanf("%d%d",&a,&b),T.Delete(a,b);
		else if (sym==2) scanf("%d",&p),printf("%d\n",T.At(p));
	}
	return 0;
}