Description

这些日子, 可可不和卡卡一起玩了, 原来可可正废寝忘食的想做一个简单而高效的文本编辑器. 你能帮助他吗? 为了明确任务目标, 可可对 “文本编辑器” 做了一个抽象的定义:

文本: 由 0 个或多个字符构成的序列. 这些字符的 ASCII 码在闭区间 \([32, 126]\) 内, 也就是说, 这些字符均为可见字符或空格.

光标: 在一段文本中用于指示位置的标记, 可以位于文本的第一个字符之前, 文本的最后一个字符之后或文本的某两个相邻字符之间.

文本编辑器: 为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序. 如果这段文本为空, 我们就说这个文本编辑器是空的.

编写一个程序: 建立一个空的文本编辑器, 从输入文件中读入一些操作指令并执行. 对所有执行过的 GET 操作, 将指定的内容写入输出文件.

Input

输入文件中第一行是指令条数 \(n\), 以下是需要执行的 \(n\) 个操作. 除了回车符之外, 输入文件的所有字符的 ASCII 码都在闭区间 \([32, 126]\) 内. 且行尾没有空格.

Output

依次对应输入文件中每条 GET 指令的输出, 不得有任何多余的字符.

Sample Input

10
Insert 13
Balanced eert
Move 2
Delete 5
Next
Insert 7
 editor
Move 0
Get
Move 11
Rotate 4
Get

Sample Output

B
t

Data Range

对输入数据我们有如下假定:

  • MOVE 操作不超过 \(50000\) 个
  • INSERT,DELETE 和 ROTATE 操作的总个数不超过 \(6000\)
  • GET 操作不超过 \(20000\) 个
  • PREV 和 NEXT 操作的总个数不超过 \(20000\)
  • 所有 INSERT 插入的字符数之和不超过 \(2^{21}\), 或 \(2097152\)
  • DELETE 操作,ROTATE 操作和 GET 操作执行时光标后必然有足够的字符
  • MOVE,PREV,NEXT 操作不会把光标移动到非法位置

输入文件没有错误.

Explanation

发现黄学长写的 STL Rope 好漂亮

所以就当了伸手党

有空学一学

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;
typedef long long lli;
const int maxn = 2000100;

int n;
char str[maxn], str_r[maxn]; // String buffer, reversed string buffer
rope<char> a, b, tmp;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    int x, pntr = 0;
    for (int idx = 1; idx <= n; idx++) {
        scanf("%s", str);
        switch(str[0]) {
            case 'M': { // Move cursor -> position
                scanf("%d", &pntr);
                break;
            } case 'P': { // Previous position
                pntr -= 1;
                break;
            } case 'N': { // Next position
                pntr += 1;
                break;
            } case 'G': { // Get output
                printf("%c\n", a[pntr]);
                break;
            } case 'I': { // Insert string
                scanf("%d", &x);
                int len = a.length();
                for (int i = 0; i < x; i++) {
                    str[i] = getchar();
                    while (str[i] == '\n')
                        str[i] = getchar();
                    str_r[x - i - 1] = str[i];
                }
                str_r[x] = str[x] = '\0';
                a.insert(pntr, str);
                b.insert(len - pntr, str_r);
                break;
            } case 'D': {
                scanf("%d", &x);
                int len = a.length();
                a.erase(pntr, x);
                b.erase(len - pntr - x, x);
                break;
            } case 'R': {
                scanf("%d", &x);
                int len = a.length();
                tmp = a.substr(pntr, x);
                a = a.substr(0, pntr) + b.substr(len - pntr - x, x) +
                    a.substr(pntr + x, len - pntr - x);
                b = b.substr(0, len - pntr - x) + tmp +
                    b.substr(len - pntr, pntr);
                break;
            } default: {
                break;
            }
        }
        continue;
    }
    return 0;
}