NOI2003Editor

2014年7月31日4,84815

Description

Input

输入文件editor.in的第一行是指令条数t，以下是需要执行的t个操作。其中：为了使输入文件便于阅读，Insert操作的字符串中可能会插入一些回车符，请忽略掉它们（如果难以理解这句话，可以参考样例）。除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。这里我们有如下假定：  MOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和NEXT操作的总个数不超过200000。  所有INSERT插入的字符数之和不超过2M（1M=1024*1024），正确的输出文件长度不超过3M字节。  DELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作必然不会试图把光标移动到非法位置。  输入文件没有错误。对C++选手的提示：经测试，最大的测试数据使用fstream进行输入有可能会比使用stdio慢约1秒。

Output

输出文件editor.out的每行依次对应输入文件中每条GET指令的输出。

Sample Input

15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 16
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22

Sample Output

.\/.
abcde^_^f.\/.ghijklmno

题解

可以用ext/rope真是极好的

stl中的****(T T 楼下有人说是可持久化平衡树)

#include<iostream>
#include<cstdio>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
crope list;
int t,now;
char ch[3000005];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    t=read();
    char s[10];int x;
    while(t--)
    {
        scanf("%s",s);
        switch(s[0])
        {
        case 'M':now=read();break;
        case 'P':now--;break;
        case 'N':now++;break;
        case 'I':
            x=read();
            for(int i=0;i<x;i++)
            {
                ch[i]=getchar();
                while(ch[i]=='\n')ch[i]=getchar();
            }
            ch[x]=0;
            list.insert(now,ch);
            break;
        case 'D':x=read();list.erase(now,x);break;
        case 'G':x=read();list.copy(now,x,ch);ch[x]=0;puts(ch);
        }
    }
    return 0;
}