记录编号	367048	评测结果	AAAAAAAAAA
题目名称	[AHOI 2006] 可可的文本编辑器	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.271 s
提交时间	2017-01-27 16:27:53	内存使用	54.65 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=3e6+10;
int n,Root,pos,top,fa[N],son[N][2],s[N];
bool rev[N];char k[N];
#define lc son[x][0]
#define rc son[x][1]
void update(int x){s[x]=s[lc]+s[rc]+1;}
void pushdown(int x){
	if (x&&rev[x]){
		if (lc) swap(son[lc][0],son[lc][1]),rev[lc]^=1;
		if (rc) swap(son[rc][0],son[rc][1]),rev[rc]^=1;
		rev[x]=0;
	}
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (y==son[z][0]) son[z][0]=x;else
	if (y==son[z][1]) son[z][1]=x;
	update(y);
	update(x);
}
void splay(int x){
	pushdown(x);
	for (;fa[x];rot(x)){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (!fa[y]||!fa[z]) continue;
		rot((x==son[y][0])==(y==son[z][0])?y:x);
	}
	Root=x;
}
void find(int R){
	int x=Root;
	while (1){
		pushdown(x);
		int i=s[lc]+1;
		if (i==R) break;
		if (R>i) x=rc,R-=i;else x=lc;
	}
	splay(x);
}
char S[N];int len;
int build(int Fa,int l,int r){
	if (l>r) return 0;
	int mid=(l+r)>>1,x=++top;
	k[x]=S[mid];fa[x]=Fa;
	lc=build(x,l,mid-1);
	rc=build(x,mid+1,r);
	update(x);
	return x;
}
void insert(){
	scanf("%d",&len);
	find(pos+1);find(pos+2);
	for (int i=1;i<=len;i++)
		for (S[i]=getchar();S[i]<32||S[i]>126;S[i]=getchar());
	int le=son[Root][0];
	son[le][1]=build(le,1,len);
	update(le);
	update(Root);
}
void move(){scanf("%d",&pos);}
void prev(){if (pos) pos--;}
void next(){if (pos<s[Root]-2) pos++;}
void filp(){
	scanf("%d",&len);
	if (pos+len+2>s[Root]) len=s[Root]-pos-2;
	find(pos+1);find(pos+len+2);
	int le=son[Root][0],th=son[le][1];
	swap(son[th][0],son[th][1]);
	rev[th]^=1;
	update(le);
	update(Root);
}
void del(){
	scanf("%d",&len);
	if (pos+len+2>s[Root]) len=s[Root]-pos-2;
	find(pos+1);find(pos+len+2);
	int le=son[Root][0];
	son[le][1]=0;
	update(le);
	update(Root);
}
void get(){
	find(pos+2);
	putchar(k[Root]);
	putchar('\n');
}
char str[10];
int main()
{
	freopen("editor.in","r",stdin);
	freopen("editor.out","w",stdout);
	scanf("%d",&n);
	Root=fa[son[1][1]=2]=1;
	s[1]=2;s[2]=1;top=2;
	for (int i=1;i<=n;i++){
		scanf("%s",str);
		if (str[0]=='M') move();
		if (str[0]=='I') insert();
		if (str[0]=='D') del();
		if (str[0]=='R') filp();
		if (str[0]=='G') get();
		if (str[0]=='P') prev();
		if (str[0]=='N') next();
	}
	return 0;
}