（splay写法）

这题和955. 维护数列一题很相似，插入，删除操作用splay可以很轻松的完成

有以下几个注意点：

1、垃圾回收机制的巧妙使用，可以防止爆空间

2、insert操作读入的字符串可能包含空格和换行符，我们不妨用getchar()函数逐个读入字符

基本操作直接套用splay的模板，此题就完成了

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2000005, INF = 127;
int nodes[N], tt;
struct Node
{
    int s[2], p;
    char v;
    int size;
    void init(char _v, int _p)
    {
        s[0] = s[1] = 0, p = _p, v = _v;
        size = 1;
    }
}tr[N];
int root, now_pos = 1, now_size = 0;
char w[1024 * 1024 * 5];
void pushup(int x)
{
    auto &u = tr[x], &l = tr[u.s[0]], &r = tr[u.s[1]];
    u.size = l.size + r.size + 1;
}
int build(int l, int r, int p)
{
    int mid = l + r >> 1;
    int u = nodes[tt -- ];
    tr[u].init(w[mid], p);
    if(l < mid) tr[u].s[0] = build(l, mid - 1, u);
    if(mid < r) tr[u].s[1] = build(mid + 1, r, u);
    pushup(u);
    return u; 
}
void rotate(int x)
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);  
}
void splay(int x, int k)
{
    while(tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if(z != k)
            if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if(!k) root = x;
}
int get_k(int k)
{
    int u = root;
    while(u)
    {
        if(tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
        else if(tr[tr[u].s[0]].size + 1 == k) return u;
        else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
}
void dfs(int u)//垃圾回收
{
    if(tr[u].s[0]) dfs(tr[u].s[0]);
    if(tr[u].s[1]) dfs(tr[u].s[1]);
    nodes[ ++ tt] = u;
}
void dfs1(int u)
{
    if(tr[u].s[0]) dfs1(tr[u].s[0]);
    printf("%c",tr[u].v);
    if(tr[u].s[1]) dfs1(tr[u].s[1]);
}
int main()
{
    int t;
    scanf("%d", &t);
    w[0] = '#',w[1] = '#';
    for(int i = 1; i < N; i ++ ) nodes[ ++ tt] = i;
    root = build(0, 1, 0);  

    char op[20];
    while(t -- )
    {
        cin >> op;
        if(*op == 'M')
        {
            int k;
            scanf("%d", &k);
            now_pos = k + 1;
        }else if(*op == 'I')
        {
            int n;
            scanf("%d", &n);
            int read_cnt = 0;
            char ch;
            while(read_cnt < n)
            {
                ch = getchar();
                if(!(ch >= 32 && ch <= 126)) continue;
                w[read_cnt ++] = ch; 
            }
            int l = get_k(now_pos - 1 + 1), r = get_k(now_pos + 1);
            splay(l, 0), splay(r, l);
            int u = build(0, n-1, r);
            tr[r].s[0] = u;
            pushup(r), pushup(l);
        }
        else if(*op == 'D')
        {
            int n;
            scanf("%d", &n);
            int l = get_k(now_pos - 1 + 1), r = get_k(now_pos + n + 1);
            splay(l, 0), splay(r, l);
            dfs(tr[r].s[0]);
            tr[r].s[0] = 0;
            pushup(r), pushup(l);
        }
        else if(*op == 'G')
        {
            int n;
            scanf("%d", &n);
            int l = get_k(now_pos - 1 + 1), r = get_k(now_pos + n + 1);
            splay(l, 0), splay(r, l);
            dfs1(tr[r].s[0]);
            puts("");
        }
        else if(*op == 'P')
        {
            now_pos --;
        }else if(*op == 'N')
        {
            now_pos ++;
        }
    }

    return 0;
}