Uva11988 Broken Keyboard (a.k.a. Beiju Text)

题目链接：传送门

分析：涉及到大量元素移动的题，如果用数组来保存，每一次修改操作一定会超时，解决这个问题的方法就是用链表，记录每个元素的下一个元素是啥，插入元素的过程：假设有i,j,我们要在i,j之间插入k,那么k的下一个就是i的下一个，i个下一个就变成了k,这道题遇到[或者]移动当前要插入的位置就好了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

char s[100010];
int nextt[100010], cur,last;

int main()
{
    while (scanf("%s", s + 1) == 1)
    {
        cur = nextt[0] = last =0;
        int sizee = strlen(s + 1);
        for (int i = 1; i <= sizee; i++)
        {
            if (s[i] == '[')
                cur = 0;
            else
                if (s[i] == ']')
                cur = last;
                else
                {
                    nextt[i] = nextt[cur];
                    nextt[cur] = i;
                    if (cur == last)
                        last = i;
                    cur = i;
                }
        }
        for (int i = nextt[0]; i; i = nextt[i])
            printf("%c", s[i]);
        printf("
");
    }

    return 0;
}