Luogu | P4567 [ AHOI 2006 ] 文本编辑器 | 数据结构 | Splay


Description

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

  • Move k:将光标移动到第 $k$ 个字符之后,如果 $k=0$,将光标移到文本第一个字符之前。
  • Insert n (换行) S:在光标后插入长度为 $n$ 的字符串 $S$ ,光标位置不变,$n \ge 1$。
  • Delete n:删除光标后的 $n$ 个字符,光标位置不变,$n \ge 1$。
  • Rotate n:反转光标后的 $n$ 个字符,光标位置不变,$n \ge 1$。
  • Get:输出光标后的一个字符,光标位置不变。
  • Prev:光标前移一个字符。
  • Next:光标后移一个字符。

下面是几个定义:

  • 文本:由 $0$ 个或多个字符构成的序列。这些字符的 ASCII 码在闭区间 $[32, 126]$ 内,也就是说,这些字符均为可见字符或空格。
  • 光标:在一段文本中用于指示位置的标记,可以位于文本的第一个字符之前,文本的最后一个字符之后或文本的某两个相邻字符之间。
  • 文本编辑器:为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空,我们就说这个文本编辑器是空的。

编写一个程序:

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

Input Format

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


Output Format

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


Input Sample

Sample 01

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


Output Sample

Sample 01

B
t


Data Range

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

  1. MOVE操作不超过 $50000$ 个,INSERT、DELETEROTATE 操作作的总个数不超过 $6000$,GET操作不超过 $20000$ 个,PREVNEXT 操作的总个数不超过 $20000$。
  2. 所有 INSERT 插入的字符数之和不超过$2$ MiB( $1$ MiB $ = 2^{20}$ Bytes)。
  3. DELETE 操作、ROTATE 操作和 GET 操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT 操作不会把光标移动到非法位置。
  4. 输入文件没有错误。

Solution

​ 很不幸的是,输入文件中操作会尝试将光标移动到非法位置,并且执行 DELETE、GETROTATE 时不保证光标后有足够的字符。在 Kth 的过程中全部返回最后的 inf 结点即可。

​ 接下来就是 Splay 普通的区间操作了。每次旋转时都需要维护下传标记。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define Rel(x) ch[fa[x]][1]==x
#define Link(x,y,z) fa[x]=y,ch[y][z]=x

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

int N;
int len;
int cnt;
int newp;
int root;
int cursor;

char c;

int fa[2097160];
int tg[2097160];
int size[2097160];
int ch[2097160][2];

char inst[10];
char val[2097160];

void Upload(int x){
    size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
    return;
}

void Download(int x){
    if(!tg[x])
        return;
    tg[ch[x][0]]^=1;
    tg[ch[x][1]]^=1;
    swap(ch[x][0],ch[x][1]);
    tg[x]=0;
    return;
}

void Rotate(int x){
    int y=fa[x];
    int z=fa[y];
    bool d=Rel(x);
    Download(x);
    Download(y);
    Link(x,z,Rel(y));
    Link(ch[x][!d],y,d);
    Link(y,x,!d);
    Upload(y);
    Upload(x);
    return;
}

void Splay(int x,int dest){
    int y,z;
    while(fa[x]!=dest){
        y=fa[x],z=fa[y];
        if(z!=dest)
            Rel(x)^Rel(y)?Rotate(x):Rotate(y);
        Rotate(x);
    }
    if(!dest)
        root=x;
    return;
}

int Kth(int k){
    int x=root;
    if(size[x]<k)
        return 2;
    while(k){
        Download(x);
        if(size[ch[x][0]]>=k)
            x=ch[x][0];
        else if(size[ch[x][0]]+1>=k)
            return x;
        else{
            k-=size[ch[x][0]]+1;
            x=ch[x][1];
        }
    }
    return 2;
}

void Delete(int k,int len){
    int Lpt=Kth(cursor);
    int Rpt=Kth(cursor+1+len);
    Splay(Lpt,0);
    Splay(Rpt,Lpt);
    ch[Rpt][0]=0;
    Upload(Rpt);
    Upload(Lpt);
    return;
}

void Reverse(int k,int Len){
    int Lpt=Kth(cursor);
    int Rpt=Kth(cursor+1+len);
    Splay(Lpt,0);
    Splay(Rpt,Lpt);
    tg[ch[Rpt][0]]^=1; // !!!
    return; 
}

int Build_Basic_Tree(){
    root=++newp;
    size[root]=2;
    size[++newp]=1;
    ch[root][1]=newp;
    fa[newp]=root;
}

int main(){
    Read(N);
    cursor=1;
    Build_Basic_Tree();
    while(N--){
        scanf("%s",inst+1);
        if(inst[1]=='M') // MOVE
            scanf("%d",&cursor),cursor++;
        if(inst[1]=='I'){ // INSERT
            cnt=0;
            scanf("%d",&len);
            int Lpt=Kth(cursor);
            Splay(Lpt,0);
            int Rpt=Kth(cursor+1);
            Splay(Rpt,Lpt);
            c=getchar();
            while(1){
                c=getchar();
                val[++newp]=c;
                fa[newp]=Rpt;
                ch[Rpt][0]=newp;
                size[fa[Rpt]]++;
                size[newp]++;
                size[Rpt]++;
                Splay(newp,0);
                cnt++;
                if(cnt==len)
                    break;
            }
        }
        if(inst[1]=='D'){ // DELETE
            scanf("%d",&len);
            Delete(cursor,len);
        }
        if(inst[1]=='R'){ // ROTATE
            scanf("%d",&len);
            Reverse(cursor,len);
        }
        if(inst[1]=='G'){ //GET
            c=val[Kth(cursor+1)];
            printf("%c",c);
            if(c!='\n')
                putchar('\n');
        }
        if(inst[1]=='P') // PRECURSOR
            cursor--;
        if(inst[1]=='N') // SUCCESSOR
            cursor++;
    }
    return 0;
}