是一道裸的Splay（反正我不会Splay，快嘲笑我！）
只需要维护在数列上加点删点操作即可，不会写Splay的渣渣只好Orz iwtwiioi大神一下了。（后来发现程序直接抄来了。。。）
就当我的第一个Splay程序吧。
1 /************************************************************** 2 Problem: 1507 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:2560 ms 7 Memory:43860 kb 8 ****************************************************************/ 9 10 #include11 #include 12 13 using namespace std; 14 char strI[1500000]; 15 16 struct Splay{ 17 struct node{ 18 node *son[2], *fa; 19 char key; 20 int size; 21 node(){ 22 son[0] = son[1] = fa = NULL; 23 size = key = 0; 24 } 25 void pushup(){ 26 size = son[0] -> size + son[1] -> size + 1; 27 } 28 29 bool d(){ 30 return this == fa -> son[1]; 31 } 32 33 void setc(node *c, int d){ 34 son[d] = c; 35 c -> fa = this; 36 } 37 } * null, *root; 38 39 Splay(){ 40 null = new node; 41 root = null; 42 root = newnode(0); 43 node *t = newnode(0); 44 root -> setc(t, 1); 45 root -> pushup(); 46 } 47 48 node *newnode(char K){ 49 node *res = new node; 50 res -> son[0] = res -> son[1] = res -> fa = null; 51 res -> key = K, res -> size = 1; 52 return res; 53 } 54 55 void rotate(node *r){ 56 node *fa = r -> fa; 57 bool d = r -> d(); 58 fa -> fa -> setc(r, fa -> d()); 59 fa -> setc(r -> son[!d], d); 60 r -> setc(fa, !d); 61 fa -> pushup(); 62 if (fa == root) root = r; 63 } 64 65 void splay(node *r, node *X){ 66 while (r -> fa != X){ 67 if (r -> fa -> fa == X) rotate(r); 68 else r -> d() == r -> fa -> d() ? (rotate(r -> fa), rotate(r)) : (rotate(r), rotate(r)); 69 } 70 r -> pushup(); 71 } 72 73 node *sel(int k){ 74 int s; 75 for(node *t = root; ;){ 76 s = t -> son[0] -> size; 77 if (s == k) return t; 78 t = t -> son[k > s]; 79 if (k > s) k -= s + 1; 80 } 81 } 82 83 node *getrange(int l, int r){ 84 node *left = sel(l); splay(left, null); 85 node *right = sel(r); splay(right, left); 86 return right; 87 } 88 89 void insert(int w, int cur){ 90 node *t = getrange(w, w + 1); 91 t -> setc(build(0, cur), 0); 92 t -> pushup(); 93 splay(t, null); 94 } 95 96 void remove(int w, int n){ 97 node *t = getrange(w, w + n + 1); 98 t -> setc(null, 0); 99 t -> pushup();100 splay(t, null);101 }102 103 node *build(int l, int r){104 if (l >= r) return null;105 int m = (l + r) >> 1;106 node *t = newnode(strI[m]);107 t -> setc(build(l, m), 0);108 t -> setc(build(m + 1, r), 1);109 t -> pushup();110 return t;111 }112 113 void print(node *r){114 if (r == null) return;115 print(r -> son[0]);116 printf("%c", r -> key);117 print(r -> son[1]);118 }119 120 void print(int w, int n){121 node *t = getrange(w, w + n + 1);122 print(t -> son[0]);123 printf("\n");124 }125 } splay;126 127 char s[10];128 129 int main(){130 int n, T, cur, w = 0;131 scanf("%d", &T);132 while (T--){133 scanf("%s", s);134 if (s[0] == 'M')135 scanf("%d", &w);136 else if (s[0] == 'P')137 --w;138 else if (s[0] == 'N')139 ++w;140 else if (s[0] == 'D'){141 scanf("%d", &n);142 splay.remove(w, n);143 } else144 if (s[0] == 'G'){ 145 scanf("%d", &n);146 splay.print(w, n);147 } else148 if (s[0] = 'I'){149 scanf("%d", &n);150 cur = 0;151 while (n--){152 while(strI[cur] = getchar(), strI[cur] == '\n');153 cur++;154 }155 splay.insert(w, cur);156 }157 }158 return 0;159 }