记录编号	173444	评测结果	AAAAAAAAAA
题目名称	[NOI 2003]文本编辑器	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	1.318 s
提交时间	2015-07-28 20:06:36	内存使用	38.43 MiB

//AUTHOR::STDAFX
//ALGORITH::SPLAY

#define MAXN 2000010UL
#define MAXL 10UL

#define ls(a) tree[a].son[0]
#define rs(a) tree[a].son[1]
#define lr ls(rs(root))

//l-1 Splay to root r+1 Splay to root's rson
//so tree lr

#include <cstdio>

struct Node{
	int son[2],pre,s;
	char key;
};

Node tree[MAXN];

char op[MAXL],ch;

int m,temp,root=1,num=2,pre,pos=1,n;

void Print(int p){
	if(!p){
		return;
	}
	Print(ls(p));printf("%c",tree[p].key);Print(rs(p));
	return;
}

void Push(int p){
	tree[p].s=tree[ls(p)].s+tree[rs(p)].s+1;
	return;
}

void Pre(){
	tree[1].pre=0;tree[1].s=2;
	rs(1)=2;tree[2].pre=1;tree[2].s=1;
	return;
}

int Find(int rt,int k){
	int Rank;
	while(true){
		Rank=tree[ls(rt)].s+1;
		if(Rank==k){
			return rt;
		}
		if(k<Rank){
			rt=ls(rt);
		}
		else{
			rt=rs(rt);k-=Rank;
		}
	}
	//rtn
}

void Rturn(int p){
	//p->p.pre
	int g=tree[p].pre;
	tree[p].pre=tree[g].pre;
	if(ls(tree[g].pre)==g){
		ls(tree[g].pre)=p;
	}
	else{
		rs(tree[g].pre)=p;
	}
	tree[g].pre=p;
	ls(g)=rs(p);rs(p)=g;tree[ls(g)].pre=g;
	Push(g);Push(p);
	return;
}

void Lturn(int p){
	//p->p.pre
	int g=tree[p].pre;
	tree[p].pre=tree[g].pre;
	if(ls(tree[g].pre)==g){
		ls(tree[g].pre)=p;
	}
	else{
		rs(tree[g].pre)=p;
	}
	tree[g].pre=p;
	rs(g)=ls(p);ls(p)=g;tree[rs(g)].pre=g;
	Push(g);Push(p);
	return;
}

void Splay(int p,int g){
	while(tree[p].pre!=g){
		if(tree[tree[p].pre].pre==g){
			if(ls(tree[p].pre)==p){
				Rturn(p);
			}
			else{
				Lturn(p);
			}
		}
		else if(ls(tree[tree[p].pre].pre)==tree[p].pre){
			Rturn(tree[p].pre);
			if(ls(tree[p].pre)==p){
				Rturn(p);
			}
			else{
				Lturn(p);
			}
		}
		else{
			Lturn(tree[p].pre);
			if(ls(tree[p].pre)==p){
				Rturn(p);
			}
			else{
				Lturn(p);
			}
		}
	}
	if(g==0){
		root=p;
	}
	return;
}

int main(){
	freopen("editor2003.in","r",stdin);
	freopen("editor2003.out","w",stdout);
	Pre();
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%s",op);
		switch(op[0]){
			case 'I':{
				//Insert n:string
				Splay(Find(root,pos),0);
				temp=rs(root);
				pre=root;
				scanf("%d",&n);
				for(int j=1;j<=n;j++){
					ch=getchar();
					while(ch<32||ch>126){
						ch=getchar();
					}
					rs(pre)=++num;
					tree[num].pre=pre;
					tree[num].key=ch;
					pre=num;
				}
				rs(pre)=temp;
				tree[temp].pre=pre;
				for(;pre;pre=tree[pre].pre){
					Push(pre);
				}
				break;
			}
			case 'M':{
				//Move to new pos
				scanf("%d",&pos);
				pos++;
				break;
			}
			case 'D':{
				//Del n
				scanf("%d",&n);
				Splay(Find(root,pos),0);
				Splay(Find(root,pos+n+1),root);
				lr=0;tree[lr].pre=0;
				break;
			}
			case 'G':{
				//Get n
				scanf("%d",&n);
				Splay(Find(root,pos),0);
				Splay(Find(root,pos+n+1),root);
				Print(lr);puts("");
				break;
			}
			case 'P':{
				pos--;
				break;
			}
			case 'N':{
				pos++;
				break;
			}
		}
	}
	return 0;
}