记录编号	222268	评测结果	AAAAAAAAAA
题目名称	[AHOI 2006] 可可的文本编辑器	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	1.117 s
提交时间	2016-01-30 06:54:04	内存使用	44.35 MiB

#define inf 2097152
#define L(x) ch[x][0]
#define R(x) ch[x][1]
#define MAXN 2100000UL

#include<cstdio>

using namespace std;

bool rev[MAXN];
char opt[15],c,seq[MAXN];int root,posl,posr;
int q,ch[MAXN][2],posn,n,fa[MAXN],siz[MAXN],sta[MAXN],pos;

inline void Swap(int &x,int &y)
{
    if(x!=y)x^=y,y^=x,x^=y;
}

inline void PushDown(int x)
{
    if(rev[x]&&x){
        rev[L(x)]^=1;
        rev[R(x)]^=1;
        Swap(L(x),R(x));
        rev[x]=false;
    }
}

inline void Update(int x)
{
    if(x)siz[x]=siz[L(x)]+siz[R(x)]+1;
}

inline void Rotate(int p,int d)
{
    int x=fa[p];
    fa[p]=fa[x];ch[fa[x]][R(fa[x])==x]=p;
    if(ch[p][d])fa[ch[p][d]]=x;
    ch[x][!d]=ch[p][d];
    ch[p][d]=x;fa[x]=p;
    Update(x);Update(p);
}

inline void Splay(int p,int f)
{
    sta[++sta[0]]=p;
    for(int i=p;i!=f;i=fa[i])
        sta[++sta[0]]=fa[i];
    while(sta[0])PushDown(sta[sta[0]--]);
    int x,y,d;
    while(fa[p]!=f){
        x=fa[p];y=fa[x];
        d=(R(x)==p);
        if(y==f)Rotate(p,!d);
        else{
            if(ch[y][d]==x)Rotate(x,!d),Rotate(p,!d);
            else Rotate(p,!d),Rotate(p,d);
        }
    }
    if(!f)root=p;
}

inline int FindKth(int rt,int kth)
{
	PushDown(rt);
    if(siz[L(rt)]+1>kth)return FindKth(L(rt),kth);
    else if(siz[L(rt)]+1<kth)return FindKth(R(rt),kth-siz[L(rt)]-1);
    else return rt;
}

inline void Insert(int len)
{
	if(!posn){
		pos=FindKth(root,1);
		Splay(pos,0);pos=0;
	}
    else{
		 pos=FindKth(root,posn);
		 Splay(pos,0);
    }
    int t=R(pos);
    while(len--){
        n++;c=getchar();
        while(c<32||c>126)c=getchar();
        seq[n]=c;
		R(pos)=n;fa[n]=pos;pos=n;
    }
    R(pos)=t;if(t)fa[t]=pos;
    while(pos)Update(pos),pos=fa[pos];
    root=R(0);
}

inline void Delete(int len)
{
	if(!posn){
		posl=FindKth(root,1);
		Splay(posl,0);posl=0;
	}
    else {
		posl=FindKth(root,posn);
		Splay(posl,0);
    }
    if(posn+len+1>siz[R(0)]-1)
        len=siz[R(0)]-posn-2;
    posr=FindKth(root,posn+len+1);
    Splay(posr,posl);
    fa[L(posr)]=0;L(posr)=0;
}

inline void Reversal(int len)
{
	if(!posn){
		posl=FindKth(root,1);
		Splay(posl,0);posl=0;
	}
    else{
		posl=FindKth(root,posn);
		Splay(posl,0);
    }
    if(posn+len+1>siz[R(0)])
        len=siz[R(0)]-posn-1;
    posr=FindKth(root,posn+len+1);
    Splay(posr,posl);
    rev[L(posr)]^=1;
}

inline void Print()
{
    int pos=FindKth(root,posn+1);
    printf("%c\n",seq[pos]);
}

inline void Debug(int rt)
{
	PushDown(rt);
	if(R(0)==inf){
		puts("空");return;
	}
	if(L(rt))Debug(L(rt));
	printf("%c",seq[rt]);
	if(R(rt))Debug(R(rt));
}

int main()
{
	freopen("editor.in","r",stdin);
	freopen("editor.out","w",stdout);
    posn=0;R(0)=inf;fa[inf]=0;
    siz[inf]=1;root=inf;siz[0]=0;
    scanf("%d",&q);
    for(int i=1,k;i<=q;i++){
        scanf("%s",opt);
        if(*opt=='P'&&posn>=1)posn--;
        else if(*opt=='N'&&posn<siz[R(0)]-1)posn++;
        else if(*opt=='G')Print();
        else if(*opt=='M')scanf("%d",&k),posn=k;
        else if(*opt=='I')scanf("%d",&k),Insert(k);
        else if(*opt=='D')scanf("%d",&k),Delete(k);
        else if(*opt=='R')scanf("%d",&k),Reversal(k);
	}
}