BZOJ 1269: [AHOI2006]文本编辑器editor 分离合并Splay

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

文本：由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32, 126]内，也就是说，这些字符均为可见字符或空格。光标：在一段文本中用于指示位置的标记，可以位于文本的第一个字符之前，文本的最后一个字符之后或文本的某两个相邻字符之间。文本编辑器：为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空，我们就说这个文本编辑器是空的。编写一个程序： 建立一个空的文本编辑器。 从输入文件中读入一些操作指令并执行。 对所有执行过的GET操作，将指定的内容写入输出文件。
Input

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

依次对应输入文件中每条GET指令的输出，不得有任何多余的字符。
Sample Input
10

Insert 13

Balanced eert

Move 2

Delete 5

Insert 7

editor

Move 0

Get

Move 11

Rotate 4

Get

Sample Output
B

HINT

对输入数据我们有如下假定： MOVE操作不超过50 000个，INSERT、DELETE和ROTATE操作作的总个数不超过6 000，GET操作不超过20 000个，PREV和NEXT操作的总个数不超过20 000。 所有INSERT插入的字符数之和不超过2M（1M=1 024*1 024）。 DELETE操作、ROTATE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作不会把光标移动到非法位置。 输入文件没有错误。

解法：维护一个支持区间分离合并翻转删除的Splay。

//BZOJ 1269 Splay

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000010;
#define key ch[ch[rt][1]][0]
int pos=1, rt=0, tot=0, n, x, ch[maxn][2], siz[maxn], fa[maxn];
bool rev[maxn];
char v[maxn], op[10], input[maxn];
void newnode(int &k, char tt, int last)
{
    k = ++tot;
    fa[k] = last;
    v[k] = tt;
    ch[k][0]=ch[k][1]=rev[k]=0;
    siz[k]=1;
}
void pushup(int k)
{
    if(!k) return;
    siz[k] = siz[ch[k][0]]+siz[ch[k][1]]+1;
}
void update(int k)
{
    if(!k) return;
    rev[k]^=1;
    swap(ch[k][0],ch[k][1]);
}
void pushdown(int k)
{
    if(!k) return;
    if(rev[k])
    {
        update(ch[k][0]);
        update(ch[k][1]);
        rev[k]=0;
    }
}
inline void rotate(int x,int &k)
{
    int y=fa[x],z=fa[y],l=(ch[y][1]==x),r=l^1;
    pushdown(y), pushdown(x);
    if (y==k) k=x;
    else ch[z][ch[z][1]==y]=x;
    fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
    ch[y][l]=ch[x][r];ch[x][r]=y;
    pushup(y);pushup(x);
}
inline void splay(int x,int &k)
{
    while (x!=k)
    {
        int y=fa[x],z=fa[y];
        if (y!=k)
        {
            if ((ch[y][0]==x)^(ch[z][0]==y)) rotate(x,k);
            else rotate(y,k);
        }
        rotate(x,k);
    }
}
int findpos(int k, int rnk){
    pushdown(k);
    int l = ch[k][0], r = ch[k][1];
    if(siz[l]+1==rnk) return k;
    else if(siz[l] >= rnk) return findpos(l, rnk);
    else return findpos(r, rnk-siz[l]-1);
}
void split(int l, int r){
    int x = findpos(rt, l-1), y = findpos(rt, r+1);
    splay(x, rt);
    splay(y, ch[rt][1]);
}
void ins(int &k, int l, int r, int last){
    int mid = (l+r)/2;
    newnode(k, input[mid], last);
    if(l<mid) ins(ch[k][0],l,mid-1,k);
    if(mid<r) ins(ch[k][1],mid+1,r,k);
    pushup(k);
}
void workins(){
    scanf("%d%*c",&x);
    gets(input);
    split(pos+1,pos);
    ins(key,0,x-1,ch[rt][1]);
    pushup(ch[rt][1]);
    pushup(rt);
}
void workdel(){
    scanf("%d%*c", &x);
    split(pos+1,pos+x);
    fa[key]=0;key=0;
    pushup(ch[rt][1]);
    pushup(rt);
}
void workrev(){
    scanf("%d%*c", &x);
    split(pos+1,pos+x);
    update(key);
}
int main()
{
    newnode(rt,'*',0);
    newnode(ch[rt][1],'*',rt);
    pushup(rt);
    scanf("%d%*c", &n);
    for(int i=1; i<=n; i++){
        scanf("%s%*c", op);
        if(op[0]=='M'){
            scanf("%d%*c",&x);
            pos=x+1;
        }
        else if(op[0]=='I'){
            workins();
        }
        else if(op[0]=='D'){
            workdel();
        }
        else if(op[0]=='R'){
            workrev();
        }
        else if(op[0]=='G'){
            printf("%c\n", v[findpos(rt,pos+1)]);
        }
        else if(op[0]=='P'){
            pos--;
        }
        else pos++;
    }
    return 0;
}