[BZOJ1507] [NOI2003] Editor (splay)

Description

[BZOJ1507] [NOI2003] Editor (splay)-LMLPHP

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 15
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

HINT

Source

Solution

　　splay的区间操作。

 #include <bits/stdc++.h>

 using namespace std;

 struct spaly

 {

     char key;

     int siz, fa, c[];

 }a[];

 char inss[];

 int ptot;

 void push_up(int k)

 {

     a[k].siz = a[a[k].c[]].siz + a[a[k].c[]].siz + ;

 }

 void rotate(int &k, int x)

 {

     int y = a[x].fa, z = a[y].fa;

     int dy = a[y].c[] == x, dz = a[z].c[] == y;

     if(k == y) k = x, a[x].fa = z;

     else a[z].c[dz] = x, a[x].fa = z;

     a[y].c[dy] = a[x].c[!dy], a[a[x].c[!dy]].fa = y;

     a[x].c[!dy] = y, a[y].fa = x;

     push_up(y);

 }

 void splay(int &k, int x)

 {

     while(k != x)

     {

         int y = a[x].fa, z = a[y].fa;

         if(k != y)

             if(a[y].c[] == x ^ a[z].c[] == y) rotate(k, x);

             else rotate(k, y);

         rotate(k, x);

     }

     push_up(x);

 }

 int find(int k, int x)

 {

     if(!k || x == a[a[k].c[]].siz + ) return k;

     if(x <= a[a[k].c[]].siz) return find(a[k].c[], x);

     return find(a[k].c[], x - a[a[k].c[]].siz - );

 }

 void build(int &k, int fa, int i, int m)

 {

     if(i == m) return;

     k = ++ptot, a[k].fa = fa, a[k].key = inss[i];

     build(a[k].c[], k, i + , m);

     push_up(k);

 }

 void printf(int k)

 {

     if(!k) return;

     printf(a[k].c[]), printf("%c", a[k].key), printf(a[k].c[]);

 }

 int main()

 {

     int n, m, root = , pos = , ctot = ;

     char op[];

     scanf("%d", &n), ptot = ;

     a[].c[] = , a[].siz = , a[].siz = , a[].fa = ;

     while(n--)

     {

         scanf("%s", op);

         if(op[] == 'M') scanf("%d", &pos);

         if(op[] == 'I')

         {

             scanf("%d", &m), ctot += m;

             for(int i = ; i < m; i++)

             {

                 inss[i] = getchar();

                 if(inss[i] <  || inss[i] > ) i--;

             }

             splay(root, find(root, pos + ));

             splay(a[root].c[], find(root, pos + ));

             build(a[a[root].c[]].c[], a[root].c[], , m);

             push_up(a[root].c[]), push_up(root);

         }

         if(op[] == 'D')

         {

             scanf("%d", &m), m = min(m, ctot - pos);

             splay(root, find(root, pos + ));

             splay(a[root].c[], find(root, pos + m + ));

             a[a[root].c[]].c[] = , ctot -= m;

             push_up(a[root].c[]), push_up(root);

         }

         if(op[] == 'G')

         {

             scanf("%d", &m), m = min(m, ctot - pos);

             splay(root, find(root, pos + ));

             splay(a[root].c[], find(root, pos + m + ));

             printf(a[a[root].c[]].c[]), puts("");

         }

         if(op[] == 'P') pos--;

         if(op[] == 'N') pos++;

     }

     return ;

 }

insert