【题解】LuoGu4008：[NOI2003]文本编辑器

原题传送门 $Splay$练手好题 光标的位置可以用一个变量$pos$表示，另，本题还需插入两个哨兵（想一想为什么） 具体做法如下

$MOVE(k)$：直接$pos=k+1$，至于为什么+1是因为最前面有一个哨兵$INSERT(n,s)$：首先得解决读入问题，之后，将光标($kth(pos)$)旋到根，将光标后继($kth(pos+1)$)旋到根的右儿子，在后继的左儿子建一棵平衡的树$DELETE(n)$：将光标旋到根，将$kth(pos+n+1)$旋到根的右儿子，$son[son[rt][1]][0]=0$，这样就把一串给删掉了$GET(n)$：同上做法，把左儿子值变成0这个操作改为$write(son[son[rt][1]][0])$，这是一个中序遍历输出的函数$PREV()$：$--pos$$NEXT()$：$++pos$

Code：

#include <bits/stdc++.h> #define maxn 2100000 using namespace std; int rt, sz, pos; int f[maxn], size[maxn], son[maxn][2]; char key[maxn]; char opt[10], s[maxn]; int get(int x){ return son[f[x]][1] == x; } int addnode(char x, int fa){ key[++sz] = x, size[sz] = 1, f[sz] = fa; return sz; } void pushup(int x){ if (x){ size[x] = 1; if (son[x][0]) size[x] += size[son[x][0]]; if (son[x][1]) size[x] += size[son[x][1]]; } } void connect(int x, int y, int z){ if (x) f[x] = y; if (y) son[y][z] = x; } void rotate(int x){ int fa = f[x], ffa = f[fa], m = get(x), n = get(fa); connect(son[x][m ^ 1], fa, m); connect(fa, x, m ^ 1); connect(x, ffa, n); pushup(fa); pushup(x); } void splay(int x, int goal){ while (f[x] != goal){ int fa = f[x]; if (f[fa] != goal) rotate(get(x) == get(fa) ? fa : x); rotate(x); } if (!goal) rt = x; } int build(char *s, int fa, int l, int r){ int mid = (l + r) >> 1; int now = addnode(s[mid], fa); if (l < mid) son[now][0] = build(s, now, l, mid - 1); if (mid < r) son[now][1] = build(s, now, mid + 1, r); pushup(now); return now; } int kth(int x){ int now = rt; while (1){ if (size[son[now][0]] >= x) now = son[now][0]; else if (size[son[now][0]] + 1 >= x) return now; else x -= size[son[now][0]] + 1, now = son[now][1]; } } void insert(int len, char *s){ int l = kth(pos), r = kth(pos + 1); splay(l, 0); splay(r, l); son[son[rt][1]][0] = build(s, son[rt][1], 1, len); pushup(son[rt][1]); pushup(rt); } void del(int x){ int l = kth(pos), r = kth(pos + x + 1); splay(l, 0); splay(r, l); son[son[rt][1]][0] = 0; pushup(son[rt][1]); pushup(rt); } void write(int x){ if (son[x][0]) write(son[x][0]); if (key[x] != '\n') putchar(key[x]); if (son[x][1]) write(son[x][1]); } void Get(int x){ int l = kth(pos), r = kth(pos + x + 1); splay(l, 0); splay(r, l); write(son[son[rt][1]][0]); puts(""); } int main(){ pos = 1; rt = addnode('\n', 0), son[rt][1] = addnode('\n', rt); int M; scanf("%d", &M); while (M--){ strcpy(s, ""); int x; scanf("%s", opt) ; if (opt[0] == 'M'){ scanf("%d", &x); pos = x + 1; } else if (opt[0] == 'I'){ scanf("%d", &x); int flag = 0; for (int i = 1; i <= x; ++i){ char c = getchar(); if (c >= 32 && c <= 126) flag = 1; if (!flag || c < 32 || c > 126){ --i; continue; } s[i] = c; } insert(x, s); } else if (opt[0] == 'D'){ scanf("%d", &x); del(x); } else if (opt[0] == 'G'){ scanf("%d", &x); Get(x); } else if (opt[0] == 'P') --pos; else ++pos; } return 0; }