题目大意：类似于我们正常输入文本，现在模拟这样的一个功能。它支持：

1.将光标移动到第k个字符前

2.在光标后面加入长度为l的字符串

3.删除光标后面l个字符

4.将光标后面l个字符翻转

5.输出光标后面的字符，并保持光标位置不变

6.将光标向前移动一个位置

7.将光标向后移动一个位置

注意：如下图所示，两次RE，得来的教训是插入的字符串长度要开到10000010-_-#

<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+u7nT0EJaT0q/07X5sKGjrLK71qq1wMqyw7TUrcDto6zX1rf7tK7X3LSmwO2yu8P3sNejrL7dy7XKx9H5wP3A78Pm09BccqGjt7TV/dP2tb2yu8yrttS+or7NtuBnZXRjaGFyKCm8uM/Cvs26w8HLo6xcclxuybXJtbfWsrvH5bP+oaOhozwvcD4KPHA+PGJyPgo8L3A+CjxwPkNPREWjujwvcD4KPHA+PGJyPgo8L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">#include #include #include #include using namespace std; struct Complex{ char val; int size; bool reverse; Complex *son[2],*father; bool Check() { return father->son[1] == this; } void Combine(Complex *a,bool dir) { son[dir] = a; a->father = this; } void Reverse() { reverse ^= 1; swap(son[0],son[1]); } }none,n,*nil = &none,*root = &n; Complex *Kth(Complex *a,int k); Complex *BuildTree(int l,int r,Complex *f); inline Complex *NewComplex(Complex *father,char x); inline void Pretreatment(); inline void SplaySeg(int x,int y); inline void Rotate(Complex *a,bool dir); inline void Splay(Complex *a,Complex *aim); inline void PushDown(Complex *a); inline void PushUp(Complex *a); void Gets(char *s); int cnt; int position; char s[10000010]; int main() { Pretreatment(); cin >> cnt; for(int x,i = 1;i <= cnt; ++i) { scanf("%s",s); switch(s[0]) { case 'M': scanf("%d",&x); position = x; break; case 'I': { char c; scanf("%d%c",&x,&c); Gets(s + 1); SplaySeg(position,position); Complex *temp = BuildTree(1,(int)strlen(s + 1),root->son[1]); root->son[1]->Combine(temp,false); PushUp(root->son[1]),PushUp(root); break; } case 'D': scanf("%d",&x); SplaySeg(position,position + x); root->son[1]->son[0]->father = nil; root->son[1]->son[0] = nil; PushUp(root->son[1]),PushUp(root); break; case 'R': scanf("%d",&x); SplaySeg(position,position + x); root->son[1]->son[0]->Reverse(); break; case 'G': Splay(Kth(root,position + 2),nil); putchar(root->val),puts(""); break; case 'P':position--; break; case 'N':position++; break; } } return 0; } inline void Pretreatment() { nil->father = nil; nil->son[0] = nil->son[1] = nil; nil->size = 0; nil->reverse = false; root->size = 2,root->val = '#'; root->Combine(NewComplex(root,'#'),true); root->son[0] = root->father = nil; } inline Complex *NewComplex(Complex *f,char x) { Complex *re = new Complex(); re->father = f; re->son[0] = re->son[1] = nil; re->val = x; re->size = 1; re->reverse = false; return re; } inline void Rotate(Complex *a,bool dir) { Complex *f = a->father; PushDown(f),PushDown(a); f->son[!dir] = a->son[dir]; f->son[!dir]->father = f; a->son[dir] = f; a->father = f->father; f->father->son[f->Check()] = a; f->father = a; PushUp(f); if(root == f) root = a; } inline void Splay(Complex *a,Complex *aim) { while(a->father != aim) { if(a->father->father == aim) Rotate(a,!a->Check()); else if(!a->father->Check()) { if(!a->Check()) Rotate(a->father,true),Rotate(a,true); else Rotate(a,false),Rotate(a,true); } else { if(a->Check()) Rotate(a->father,false),Rotate(a,false); else Rotate(a,true),Rotate(a,false); } } PushUp(a); } Complex *Kth(Complex *a,int k) { PushDown(a); if(k <= a->son[0]->size) return Kth(a->son[0],k); k -= a->son[0]->size; if(k == 1) return a; return Kth(a->son[1],k - 1); } Complex *BuildTree(int l,int r,Complex *f) { if(l > r) return nil; int mid = (l + r) >> 1; Complex *re = NewComplex(f,s[mid]); re->Combine(BuildTree(l,mid - 1,re),false); re->Combine(BuildTree(mid + 1,r,re),true); PushUp(re); return re; } inline void PushDown(Complex *a) { if(a == nil) return ; if(a->reverse) { if(a->son[0] != nil) a->son[0]->Reverse(); if(a->son[1] != nil) a->son[1]->Reverse(); a->reverse = false; } } inline void PushUp(Complex *a) { if(a == nil) return ; a->size = a->son[0]->size + a->son[1]->size + 1; } inline void SplaySeg(int x,int y) { Splay(Kth(root,x + 1),nil); Splay(Kth(root,y + 2),root); } void Gets(char *s) { char c; while(c = getchar(),c != '\n') *s++ = c; *s = '\0'; }