记录编号	23008	评测结果	AAAAAAAAAA
题目名称	[AHOI 2006] 可可的文本编辑器	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.501 s
提交时间	2011-02-23 13:37:08	内存使用	58.32 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;

const int maxn=1024*1024*2;
int now=0;

struct node
{
	char ch;
	int size;
	bool rev;
	node *c[2],*f;
}E[maxn],*root,*null,*V[maxn];
int eh;
char a[maxn];int vh;

void down(node *p)
{
	if (p==null) return;
	if (p->rev)
	{
		node *q=p->c[0];
		p->c[0]=p->c[1];
		p->c[1]=q;
		p->c[0]->rev=!p->c[0]->rev;
		p->c[1]->rev=!p->c[1]->rev;
		p->rev=false;
	}
}

void rot(node *p,int o)
{
	node *q=p->f;
	q->c[o]=p->c[!o];
	p->c[!o]->f=q;
	p->c[!o]=q;
	p->f=q->f;
	if (q==p->f->c[o]) p->f->c[o]=p;
	else p->f->c[!o]=p;
	q->f=p;
	p->c[!o]=q;
	if (q!=null) q->size=q->c[0]->size+q->c[1]->size+1;
	if (p!=null) p->size=p->c[0]->size+p->c[1]->size+1;
	if (q==root) root=p;
}

node *newnode(char ch,node *f)
{
	node *p=&E[++eh];
	p->ch=ch;
	p->c[1]=p->c[0]=null;
	p->f=f;
	p->size=1;
	p->rev=false;
	return p;
}

void splay(node *p,node *q)
{
	down(p);
	while (p->f!=q)
	{
		if (p->f->f==q)
		{
			if (p==p->f->c[0]) rot(p,0);
			else rot(p,1);
		}
		else
		{
			if (p->f->f->c[0]==p->f)
			{
				if (p==p->f->c[0]) rot(p->f,0),rot(p,0);
				else rot(p,1),rot(p,0);
			}
			else
			{
				if (p==p->f->c[1]) rot(p->f,1),rot(p,1);
				else rot(p,0),rot(p,1);
			}
		}
	}
}

void select(int k,node *q)
{
	node *p=root;
	down(p);
	while (k!=p->c[0]->size+1)
	{
		if (k<p->c[0]->size+1) p=p->c[0];
		else k-=p->c[0]->size+1,p=p->c[1];
		down(p);
	}
	splay(p,q);
}

void ins(int n,char *A)
{
	select(now+1,null);
	select(now+2,root);
	node *p=root->c[1];
	for (;n>0;--n)
	{
		p=newnode(A[n],p);
		p->f->c[0]=p;
	}
	splay(p,null);
}

void del(int n)
{
	select(now+1,null);
	select(now+n+2,root);
	root->c[1]->c[0]=null;
	splay(root->c[1],null);
}

void get()
{
	select(now+2,null);
	printf("%c\n",root->ch);
}

void ro(int n)
{
	select(now+1,null);
	select(now+n+2,root);
	root->c[1]->c[0]->rev=!root->c[1]->c[0]->rev;
	splay(root->c[1]->c[0],null);
}

void init()
{
	null=newnode(' ',0);
	null->size=0;
	root=newnode(' ',null);
	root->c[1]=newnode(' ',root);
	splay(root->c[1],null);
}

int main()
{
	freopen("editor.in","r",stdin);
	freopen("editor.out","w",stdout);
	init();
	int T,t,n;
	char w[11];
	scanf("%d",&T);
	for (;T;--T)
	{
		scanf("%s",w);
		if (w[0]=='I')
		{
			scanf("%d",&t);
			n=t;
			while (t)
			{
				scanf("%c",a+(n-t+1));
				if (a[n-t+1]!=10 && a[n-t+1]!=13) --t;
			}
			ins(n,a);
		}
		else if (w[0]=='M')
		{
			scanf("%d",&t);
			now=t;
			select(now+1,null);
		}
		else if (w[0]=='D')
		{
			scanf("%d",&t);
			del(t);
		}
		else if (w[0]=='G')
		{
			get();
		}
		else if (w[0]=='R')
		{
			scanf("%d",&t);
			ro(t);
		}
		else if (w[0]=='P') --now,select(now+1,null);
		else ++now,select(now+1,null);
	}
	return 0;
}