记录编号	27196	评测结果	AAEEAAAEEE
题目名称	[NOI 2003]文本编辑器	最终得分	50
用户昵称	Pom	是否通过	未通过
代码语言	C++	运行时间	3.660 s
提交时间	2011-08-04 18:05:51	内存使用	81.37 MiB

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

using namespace std;

const int MAXP=3000000;

int Q,i,j,k,now,op;
char ch,st[1024*1024];

struct node
{
	char C;
	int size;
	node *c[2],*f;
	node()
	{
		c[0]=c[1]=f=NULL;
	}
	inline void update()
	{
		size=1;
		if (c[0]) size+=c[0]->size;
		if (c[1]) size+=c[1]->size;
	}
};

struct stack  
{  
    node *v; 
    bool l,r;  
    stack()  
    {  
        l=r=false;  
        v=NULL;  
    }  
}S[MAXP]; 

struct Splay
{
	node P[MAXP],*root,*temp;
	int ps,h;
	Splay()
	{
		root=P;
		root->size=2;
		root->c[1]=P+1;
		P[1].size=1;
		P[1].f=root;
		ps=1;
	}
	void rotate(node *p,int d)
	{
		p->f->c[!d]=p->c[d];
		if (p->c[d]) p->c[d]->f=p->f;
		if (p->f->f)
		{
			if (p->f->f->c[d]==p->f) p->f->f->c[d]=p;
			else p->f->f->c[!d]=p;
		}
		p->c[d]=p->f;
		p->f=p->c[d]->f;
		p->c[d]->f=p;
		p->c[d]->update();
		p->update();
	}
	void splay(node *p,node *goal)
	{
		while (p->f!=goal)
		{
			if (p->f->f==goal)
			{
				if (p->f->c[0]==p) rotate(p,1);
				else rotate(p,0);
			}
			else
			{
				if (p->f->c[1]==p)
				{
					if (p->f->f->c[1]==p->f)
					{
						rotate(p->f,0);
						rotate(p,0);
					}
					else
					{
						rotate(p,0);
						rotate(p,1);
					}
				}
				else
				{
					if (p->f->f->c[0]==p->f)
					{
						rotate(p->f,1);
						rotate(p,1);
					}
					else
					{
						rotate(p,1);
						rotate(p,0);
					}
				}
			}
		}
		if (goal==NULL) root=p;
	}
	node* find(int key)
	{
		node *p=root;
		int now=0;
		for (;;)
		{
			if (p->c[0])
			{
				if (p->c[0]->size+1+now==key) return p;
				if (p->c[0]->size+now>=key) p=p->c[0];
				else
				{
					now+=1+p->c[0]->size;
					p=p->c[1];
				}
				continue;
			}
			if (now+1==key) return p;
			++now;
			p=p->c[1];
		}
	}
	void roll(int x,int y)
	{
		splay(find(x),NULL);
		splay(find(y),root);
	}
	void makestring(int n)
	{
		temp=P+ps+1;
		for (int i=0;i<n;i++)
		{
			scanf("%c",&ch);
			while ((int) ch<32 || (int) ch>126) scanf("%c",&ch);
			++ps;
			P[ps].C=ch;
			P[ps].size=n-i;
			if (i<n-1)
			{
				P[ps].c[1]=P+ps+1;
				P[ps+1].f=P+ps;
			}
		}
	}
	void dfs(node *p)  
  	{  
        	h=0;  
		S[++h].v=p;  
		S[h].l=S[h].r=false;  
		while (h)  
		{  
			if (S[h].r)  
			{  
				--h;  
				continue;  
			}  
			if (!S[h].v->c[0] && !S[h].v->c[1])  
			{  
				printf("%c",S[h--].v->C);  
				continue;  
			}  
			else  
				if (!S[h].v->c[0])  
				{  
					printf("%c",S[h].v->C);  
					S[++h].v=S[h-1].v->c[1];  
					S[h-1].r=true;  
					S[h].l=S[h].r=false;  
					continue;  
				}  
		        	else  
					if (!S[h].v->c[1])  
					{  
						if (S[h].l)   
						{  
							printf("%c",S[h--].v->C);  
							continue;  
						}  
						else  
						{  
							S[++h].v=S[h-1].v->c[0];  
							S[h].l=S[h].r=false;  
							S[h-1].l=true;  
							continue;  
						}  
					}  
					else  
					{  
						if (S[h].l)  
						{  
							printf("%c",S[h].v->C);  
							S[++h].v=S[h-1].v->c[1];  
							S[h-1].r=true;  
							S[h].l=S[h].r=false;  
							continue;  
						}  
						else  
						{  
							S[++h].v=S[h-1].v->c[0];  
							S[h].l=S[h].r=false;  
							S[h-1].l=true;  
							continue;  
						}  
					}  
		}  
	}  
}T;

inline void Move()
{
	scanf("%s%d",st,&op);
	now=op+1;
}

void Insert()
{
	scanf("%s%d",st,&op);
	T.makestring(op);
	T.roll(now,now+1);
	T.root->c[1]->c[0]=T.temp;
	T.temp->f=T.root->c[1];
	T.root->c[1]->update();
	T.root->update();
}

void Delete()
{
	scanf("%s%d",st,&op);
	T.roll(now,now+op+1);
	T.root->c[1]->c[0]=NULL;
	T.root->c[1]->update();
	T.root->update();
}

void Get()
{
	scanf("%s%d",st,&op);
	T.roll(now,now+op+1);
	T.dfs(T.root->c[1]->c[0]);
	printf("\n");
}

int main()
{
	freopen("editor2003.in","r",stdin);
	freopen("editor2003.out","w",stdout);
	scanf("%d",&Q);
	now=1;
	while (Q--)
	{
		scanf("%c",&ch);
		while (ch!='M' && ch!='I' && ch!='D' && ch!='G' && ch!='P' && ch!='N') scanf("%c",&ch);
		if (ch=='P') --now;
		if (ch=='N') ++now;
		if (ch=='M') Move();
		if (ch=='I') Insert();
		if (ch=='G') Get();
		if (ch=='D') Delete();
	}
	return 0;
}