记录编号	300973	评测结果	AAAAAAAAAA
题目名称	[NOI 2003]文本编辑器	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.043 s
提交时间	2016-08-29 16:52:06	内存使用	60.37 MiB

#include<cstdio>
#include<cstring>
const int N=3000010;
int t,l,q[N];bool m[N];
char ch[N],S[N],a[N];
struct Splay{
	char ch[N];
	int l[N],r[N],s[N],root,top,_x;
	Splay(){
		memset(l,0,sizeof l);
		memset(r,0,sizeof r);
		memset(ch,0,sizeof ch);
		memset(s,0,sizeof s);
		_x=root=1;top=r[1]=s[1]=2;s[2]=1;
	}
	inline void update(int x){
		s[x]=s[l[x]]+s[r[x]]+1;
	}
	inline void l_rotate(int &x){
		int y=r[x];
		r[x]=l[y];l[y]=x;
		update(y);update(x);
		x=y;
	}
	inline void r_rotate(int &x){
		int y=l[x];
		l[x]=r[y];r[y]=x;
		update(y);update(x);
		x=y;
	}
	void splay(int &x,int pos){
		int i=s[l[x]]+1;
		if (i==pos) return;
		if (i<pos) splay(r[x],pos-i),l_rotate(x);
			else splay(l[x],pos),r_rotate(x);
	}
	int build(int L,int R){
		if (L>R) return 0;
		int mid=(L+R)/2,now=++top;
		ch[now]=S[mid];s[now]=R-L+1;
		l[now]=build(L,mid-1);
		r[now]=build(mid+1,R);
		return now;
	}
	inline void insert(int len){
		splay(root,_x);
		splay(root,_x+1);
		for (int i=1;i<=len;i++)
		for (S[i]=0;S[i]<32||S[i]>126;S[i]=getchar());
		r[l[root]]=build(1,len);
		update(l[root]);
		update(root);
	}
	inline void del(int len){
		splay(root,_x);
		splay(root,_x+len+1);
		r[l[root]]=0;
		update(l[root]);
		update(root);
	}
	inline void move(int pos){_x=pos+1;}
	inline void next(){_x++;}
	inline void prev(){_x--;}
	inline void get(int len){
		splay(root,_x);
		splay(root,_x+len+1);
		print(r[l[root]]);
		puts("");
	}
	void print(int x){
		if (l[x]) print(l[x]);
		putchar(ch[x]);
		if (r[x]) print(r[x]);
	}
}T;
int main()
{
	freopen("editor2003.in","r",stdin);
	freopen("editor2003.out","w",stdout);
	scanf("%d",&t);
	while (t--){
		scanf("%s",ch);
		if (ch[0]!='P'&&ch[0]!='N') scanf("%d",&l);
		gets(a);
		if (ch[0]=='I') T.insert(l);
		if (ch[0]=='D') T.del(l);
		if (ch[0]=='G') T.get(l);
		if (ch[0]=='M') T.move(l);
		if (ch[0]=='P') T.prev();
		if (ch[0]=='N') T.next();
	}
	return 0;
}