题目大意：维护一种数据结构，它可以：
1.移动光标
2.在光标之后插入一段字符串
3.删除光标之后的n个字符
4.输出光标之后的n个字符
5.移动光标
思路：Splay，没什么特别的。但是有几个需要注意的地方。1.题中说：delete操作不会越界。但是其实有可能会越界，比如样例就越界了。。
2.输出的时候一定不要偷懒。我刚开始写的时候就把输出写成nlogn输出的了，然后果断T了吗，我还以为是哪里死循环了，结果是这里被卡了！以后再也不偷懒随便加logn了。。。
CODE：
#include
#include
#include
#include
#define MAX (1 << 22|100) using namespace std; struct Complex{ char c; int size; Complex *son[2],*father; void Combine(Complex *a,bool dir) { son[dir] = a; a->father = this; } bool Check() { return father->son[1] == this; } void PushUp() { size = son[0]->size + son[1]->size + 1; } }*nil = new Complex(),*root; void Pretreatment(); Complex *BuildTree(int l,int r); Complex *Kth(Complex *a,int k); Complex *NewComplex(char val); inline void Rotate(Complex *a,bool dir); inline void Splay(Complex *a,Complex *aim); void Print(Complex *a); char src[MAX]; int asks,now; char s[MAX]; int main() { Pretreatment(); cin >> asks; for(int x,i = 1;i <= asks; ++i) { scanf("%s",s); if(s[0] == 'M') scanf("%d",&now); else if(s[0] == 'I') { scanf("%d",&x); for(int j = 1;j <= x; ++j) while(scanf("%c",&src[j]),src[j] < 32); Splay(Kth(root,now + 1),nil); Splay(Kth(root,now + 2),root); root->son[1]->Combine(BuildTree(1,x),false); root->son[1]->PushUp(); root->PushUp(); } else if(s[0] == 'D') { scanf("%d",&x); Splay(Kth(root,now + 1),nil); Splay(Kth(root,min(root->size,now + x + 2)),root); root->son[1]->son[0] = nil; root->son[1]->PushUp(); root->PushUp(); } else if(s[0] == 'G') { scanf("%d",&x); Splay(Kth(root,now + 1),nil); Splay(Kth(root,min(now + x + 2,root->size)),root); Print(root->son[1]->son[0]); puts(""); } else if(s[0] == 'P') --now; else ++now; } return 0; } void Pretreatment() { root = BuildTree(1,2); root->father = nil; nil->father = nil->son[0] = nil->son[1] = nil; nil->size = 0; } Complex *BuildTree(int l,int r) { if(l > r) return nil; int mid = (l + r) >> 1; Complex *re = NewComplex(src[mid]); re->Combine(BuildTree(l,mid - 1),false); re->Combine(BuildTree(mid + 1,r),true); re->PushUp(); return re; } Complex *Kth(Complex *a,int k) { 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 *NewComplex(char val) { Complex *re = new Complex(); re->c = val; re->size = 1; re->son[0] = re->son[1] = nil; return re; } inline void Rotate(Complex *a,bool dir) { Complex *f = a->father; 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; f->PushUp(); 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); } } a->PushUp(); } void Print(Complex *a) { if(a == nil) return ; Print(a->son[0]); putchar(a->c); Print(a->son[1]); }