文本编辑器问题

解题思路

本题要我们模拟一个记事本，用一个字符串来表示记事本中的内容，最开始是空的。字符串中存在一个光标。

我们要实现六种操作，第一个操作是将光标移动到第 $k$ 个字符后面。第二个操作是在当前光标的后面插入一个长度为 $n$ 的字符串且光标位置不变。第三个操作是删除光标后面的 $n$ 个字符且光标位置不变。第四个操作是输出光标后的 $n$ 个字符且光标位置不变。第五个操作是将光标前移一个字符，第六个操作是将光标后移一个字符。

首先我们需要维护一个光标所在的位置，我们可以将光标所在的位置表示为在第几个字符后面，但是当光标在最左边时，此时光标前面没有字符，为了便于处理这种特殊情况，我们可以在最开始先插入一个字符，这样光标最靠左也就在第一个字符的后面，我们就能统一维护光标所在的位置。

可以发现本题需要执行的修改操作只有快速插入和删除某一段序列，对于这个操作是可以用平衡树来做的，但是由于本题只有这两种操作，并没有更多需要用到平衡树的操作，因此本题更应该用块状链表来做，块状链表的作用就是能快速插入和删除某一段序列。

确定用块状链表后，我们需要考虑一下每个块中需要维护的信息，首先每个块中需要存储块中的元素，本题的每个元素都是字符，因此用一个 char 数组来存储块中所有元素，题目保证字符串总长度最大是两百万，开个根号就是一千多，由于块状链表中每个块的长度并不固定，因此每一个块存储的字符串长度可以开到两千。我们还需要记录块内真实的字符串长度 $cnt$，由于每个块都是链表中的节点，因此我们还需要存储两个指针 $l, r$ 表示左、右节点。

然后就能开始处理题目要求的各种操作，对于操作一，就是将光标移动到第 $k$ 个字符后面，直接更新光标的信息即可，对于光标，我们应该存两个信息 $x, y$ 分别表示在第几块和在块内第几个字符后面。直接从头开始枚举所有块找到光标应该存在的位置即可，时间复杂度是 $\sqrt{n}$ 级别的。

对于操作二，在光标后面插入一段字符，如果光标不在所在块的末尾，就将所在块从光标位置断开成两小块，然后在两小块之间插入新的字符组成的块状链表即可。

对于操作三，删除光标后面的一段字符，直接枚举需要删除的字符所在的所有块，对于完整块可以直接删去，对于需要删去一部分的头、尾两个块则直接暴力枚举内部元素进行删除即可。

对于操作四，输出光标后面一段字符，这个操作其实和删除操作类似，只不过将删除改成输出。

对于操作五、六，如果移动后还在同一个块内部，则只需要修改 $y$，如果移动后会进入相邻的块内部，则需要对 $x, y$ 都进行修改。

综上所述，我们就能用块状链表实现所有操作，前面四个操作的时间复杂度都是 $O(\sqrt{n})$ 的，最后两个操作则是 $O(1)$ 的。

注意，本题的操作次数很多，虽然字符串总长度不会超过两百万，但是内部插入删除操作很多，因此每个下标可能会用到多次，因此可以用一个栈来进行内存回收，节省一些内存。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2000, M = 2010;

struct Node
{
    char s[N + 1]; //块内存储的连续字符串
    int c, l, r; //块内真实字符数量、左节点、右节点
}p[M]; //链表节点

int n, x, y; //操作数、光标在第几块、光标在块内第几个字符后面
char str[2000010];
int q[M], tt; //内存回收机制

void move(int k) //将光标移动到第 k 个字符后面
{
    x = p[0].r; //从起始节点开始找第 k 个字符所在的位置
    while(k > p[x].c) k -= p[x].c, x = p[x].r;
    y = k - 1; //块内字符下标从 0 开始，第 k 个字符下标是 k - 1
}

void add(int x, int u) //将节点 u 插入到节点 x 的后面
{
    p[u].r = p[x].r, p[p[u].r].l = u;
    p[x].r = u, p[u].l = x;
}

void del(int u) //将节点 u 从链表中删除
{
    p[p[u].l].r = p[u].r;
    p[p[u].r].l = p[u].l;
    p[u].l = p[u].r = p[u].c = 0; //清空节点 u 的信息
    q[++tt] = u; //将下标 u 放入内存回收站
}

void insert(int k) //在光标后面插入 k 个字符
{
    if(y < p[x].c - 1) //如果光标不在某一块的最后，就将光标所在的块从光标处分裂
    {
        int u = q[tt--]; //新建一个节点用来存储分裂出的后半部分
        for(int i = y + 1; i < p[x].c; i++) //将分裂出的后半部分复制到新节点中
            p[u].s[p[u].c++] = p[x].s[i];
        p[x].c = y + 1; //原节点只剩下前半部分，更新长度
        add(x, u); //将新建的节点插入到 x 的后面
    }

    int cur = x; //记录当前所在节点，每次在当前节点后面插入一个新的节点
    for(int i = 0; i < k; )
    {
        int u = q[tt--]; //新建一个块
        while(p[u].c < N && i < k) //将新的块塞满
            p[u].s[p[u].c++] = str[i++];
        add(cur, u); //将新的块插入当前节点的后面
        cur = u; //更新当前所在节点（指针走向后一个块）
    }
}

void remove(int k) //将光标后面 k 个字符删除
{
    if(p[x].c - y - 1 >= k) //如果光标后面 k 个字符和光标在同一个块内，直接内部删除
    {
        for(int i = y + k + 1, j = y + 1; i < p[x].c; i++, j++) p[x].s[j] = p[x].s[i];
        p[x].c -= k;
    }
    else //否则需要跨块删除（分三步删除）
    {
        k -= p[x].c - y - 1; //删除开头节点的后半部分（第一部分）
        p[x].c = y + 1; //更新长度
        while(p[x].r && k >= p[p[x].r].c) //删除中间的整段部分（第二部分）
        {
            k -= p[p[x].r].c;
            del(p[x].r);
        }
        //删除结尾节点的前半部分（第三部分）
        int u = p[x].r;
        for(int i = 0, j = k; j <= p[u].c; i++, j++) p[u].s[i] = p[u].s[j]; //将剩余的后半部分移到前面
        p[u].c -= k; //更新长度
    }
}

void get(int k) //输出光标后面 a 个字符
{
    if(p[x].c - y - 1 >= k) //如果光标后面 k 个字符和光标在同一个块内，直接内部输出
    {
        for(int i = y + 1; i <= y + k; i++) putchar(p[x].s[i]);
    }
    else //否则需要跨块输出（分三步输出）
    {
        k -= p[x].c - y - 1;
        for(int i = y + 1; i < p[x].c; i++) putchar(p[x].s[i]); //输出开头节点的后半部分（第一部分）
        int cur = x;
        while(p[x].r && k >= p[p[x].r].c) //输出中间的整段部分（第二部分）
        {
            int u = p[cur].r;
            for(int i = 0; i < p[u].c; i++) putchar(p[u].s[i]);
            k -= p[u].c;
            cur = u;
        }
        //删除结尾节点的前半部分（第三部分）
        int u = p[cur].r;
        for(int i = 0; i < k; i++) putchar(p[u].s[i]);
    }
    puts("");
}

void prev() //将光标前移一个字符
{
    if(!y)
    {
        x = p[x].l;
        y = p[x].c - 1;
    }
    else y--;
}

void next() //将光标后移一个字符
{
    if(y < p[x].c - 1) y++;
    else
    {
        x = p[x].r;
        y = 0;
    }
}

void merge() //将链表中较短的节点合并
{
    for(int i = p[0].r; i; i = p[i].r) //枚举每个节点
    {
        while(p[i].r && p[i].c + p[p[i].r].c < N) //如果当前节点和后一节点的长度和不超过长度限制，则可以合并
        {
            int r = p[i].r;
            for(int j = p[i].c, k = 0; k < p[r].c; j++, k++) p[i].s[j] = p[r].s[k];
            if(x == r) x = i, y += p[i].c; //如果光标在后一节点中，更新光标位置
            p[i].c += p[r].c; //更新当前节点的长度
            del(r); //删除后一节点
        }
    }
}

int main()
{
    //最开始所有下标都可以使用，先全部加入内存回收站
    for(int i = 1; i < M; i++) q[++tt] = i;

    scanf("%d", &n);

    str[0] = '*'; //插入一个哨兵，用于处理光标在最左边时的边界情况
    insert(1); //插入哨兵
    move(1); //将光标移动到哨兵后面

    char op[10];
    while(n--)
    {
        int a;
        scanf("%s", op);
        if(!strcmp(op, "Move")) //将光标移动到第 a 个字符后面
        {
            scanf("%d", &a);
            move(a + 1); //算上哨兵应该是第 a + 1 个字符后面
        }
        else if(!strcmp(op, "Insert")) //在光标后面插入 a 个字符
        {
            scanf("%d", &a);
            //接收要插入的字符串
            int i = 0, k = a;
            while(a)
            {
                str[i] = getchar();
                if(str[i] >= 32 && str[i] <= 126) i++, a--; //只考虑合法范围内的字符
            }
            insert(k); //将字符插入第 k 个字符后面
            merge(); //将链表中较短的节点合并
        }
        else if(!strcmp(op, "Delete")) //将光标后面 a 个字符删除
        {
            scanf("%d", &a);
            remove(a); //将光标后面 a 个字符删除
            merge(); //将链表中较短的节点合并
        }
        else if(!strcmp(op, "Get")) //输出光标后面 a 个字符
        {
            scanf("%d", &a);
            get(a);
        }
        else if(!strcmp(op, "Prev")) prev(); //将光标前移一个字符
        else next(); //将光标后移一个字符
    }
    return 0;
}