\(Splay\)先练到这吧（好像还有道毒瘤的维护数列诶，算了吧）
记录下光标的编号，维护就是
\(Splay\)基操了。
另外数据有坑，数据是
\(Windows\)下生成了，回车是'\n\r'，我就被坑了。
#include #include using namespace std;inline int read(){ int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();} while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar(); return s * w;}const int MAXINSERTLEN = 10000010;struct SplayTree{ char val; int ch[2], fa, size;}t[MAXINSERTLEN];char str[MAXINSERTLEN];int num, root, n, len;void pushup(int u){ t[u].size = t[t[u].ch[0]].size + t[t[u].ch[1]].size + 1;}void rotate(int x){ int y = t[x].fa; int z = t[y].fa; int k = t[y].ch[1] == x; t[z].ch[t[z].ch[1] == y] = x; t[x].fa = z; t[y].ch[k] = t[x].ch[k ^ 1]; t[t[x].ch[k ^ 1]].fa = y; t[x].ch[k ^ 1] = y; t[y].fa = x; pushup(y); pushup(x);}void Splay(int x, int goal){ while(t[x].fa != goal){ int y = t[x].fa; int z = t[y].fa; if(z != goal) (t[z].ch[0] == y) ^ (t[y].ch[0] == x) ? rotate(x) : rotate(y); rotate(x); } if(goal == 0) root = x;}int build(int l, int r){ int id = ++num; int mid = (l + r) >> 1; t[id].val = str[mid]; if(mid > l){ t[id].ch[0] = build(l, mid - 1); t[t[id].ch[0]].fa = id; } if(mid < r){ t[id].ch[1] = build(mid + 1, r); t[t[id].ch[1]].fa = id; } pushup(id); return id;}inline int findKth(int k){ int u = root; while(1){ if(t[t[u].ch[0]].size >= k) u = t[u].ch[0]; else if(t[t[u].ch[0]].size == k - 1) return u; else k -= t[t[u].ch[0]].size + 1, u = t[u].ch[1]; }}inline int next(int x, int mode){ Splay(x, 0); int u = t[x].ch[mode]; mode ^= 1; while(t[u].ch[mode]) u = t[u].ch[mode]; return u;}char opt;int cur;void print(int x){ if(t[x].ch[0]) print(t[x].ch[0]); if(t[x].val != 1) printf("%c", t[x].val); if(t[x].ch[1]) print(t[x].ch[1]);}int main(){ n = read(); root = cur = ++num; t[num].val = 1; t[++num].fa = cur; t[num].val = 1; t[cur].ch[1] = num; t[num].size = 1; t[cur].size = 2; for(int i = 1; i <= n; ++i){ opt = getchar(); while(opt < 'A' || opt > 'Z') opt = getchar(); if(opt == 'I'){ len = read(); for(int i = 1; i <= len; ++i){ str[i] = getchar(); while(str[i] < 32 || str[i] > 126) str[i] = getchar(); } Splay(cur, 0); Splay(next(cur, 1), cur); t[t[root].ch[1]].ch[0] = (len = build(1, len)); t[len].fa = t[root].ch[1]; Splay(t[t[root].ch[1]].ch[0], 0); } else if(opt == 'G'){ len = read(); Splay(cur, 0); Splay(findKth(t[t[root].ch[0]].size + 2 + len), root); print(t[t[root].ch[1]].ch[0]); putchar('\n'); } else if(opt == 'M') cur = findKth(read() + 1); else if(opt == 'P') cur = next(cur, 0); else if(opt == 'N') cur = next(cur, 1); else if(opt == 'D'){ len = read(); Splay(cur, 0); Splay(findKth(t[t[root].ch[0]].size + 2 + len), root); t[t[root].ch[1]].ch[0] = 0; } } return 0;}