BZOJ 1507 [NOI2003]Editor

题目大意

给你一个文本，让你维护它，支持以下操作：插入字符串；删除字符串；输出字符。

直接Splay维护一下就可以完美解决了qwq

注意对于这种一次插入一大堆东西的一定要O(N)建一棵新Splay树之后再合并到根节点右儿子的左儿子的位置，之后就可以了。1269查询的是字符串，跑一次DFS中序遍历输出就可以了。

#include <bits/stdc++.h>
using namespace std;
int n,inx,point,siz[2100000],son[2100000][2],fa[2100000],root,tot=2;
char mode[10],s[2100000],val[2100000];
bool rev[2100000];
void rever(int pos) {swap(son[pos][0],son[pos][1]),rev[pos]^=1;return;}
void pushup(int pos) {siz[pos]=siz[son[pos][0]]+siz[son[pos][1]]+1;return;}
void pushdown(int pos) {if(rev[pos]) rever(son[pos][0]),rever(son[pos][1]),rev[pos]=0;return;}
void rotate(int &rt,int x)
{
    int y=fa[x],z=fa[y],l=(son[y][1]==x),r=l^1;
    if(y==rt) rt=x;
    else son[z][son[z][1]==y]=x;
    fa[x]=z,fa[y]=x,fa[son[x][r]]=y,son[y][l]=son[x][r],son[x][r]=y;
    pushup(y),pushup(x);
}
void splay(int &k,int x)
{
    while(x!=k)
    {
        int y=fa[x],z=fa[y];
        if(y!=k)
        {
            if((son[y][0]==x)^(son[z][0]==y)) rotate(k,x);
            else rotate(k,y);
        }
        rotate(k,x);
    }
}
int lookfor(int pos,int tx)
{
    pushdown(pos);
    if(tx<=siz[son[pos][0]]) return lookfor(son[pos][0],tx);
    if(tx>siz[son[pos][0]]+1) return lookfor(son[pos][1],tx-siz[son[pos][0]]-1);
    return pos;
}
int split(int tx,int ty)
{
    splay(root,lookfor(root,tx)),splay(son[root][1],lookfor(root,ty+2));
    return son[son[root][1]][0];
}
void readin()
{
    char tmp=getchar();
    while(tmp<32||tmp>126) tmp=getchar();
    inx--;
    for(int i=0;i<inx;++i)
    {
        s[i]=tmp,tmp=getchar();
        while(tmp=='\n') tmp=getchar();
    }
    s[inx]=tmp;
    inx++;
}
int build(int l,int r)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    son[mid][0]=build(l,mid-1);
    son[mid][1]=build(mid+1,r);
    fa[son[mid][0]]=fa[son[mid][1]]=mid;
    pushup(mid);
    return mid;
}
void dfs(int pos)
{
    if(pos==0) return;
    dfs(son[pos][0]);
    printf("%c",val[pos]);
    dfs(son[pos][1]);
}
int main()
{
    scanf("%d",&n);
    root=build(1,2);
    tot=2;
    while(n--)
    {
        scanf("%s",mode);
        switch(mode[0])
        {
            case 'M': {scanf("%d",&inx);point=inx;break;}
            case 'I':
            {
                scanf("%d",&inx);
                readin();
                split(point+1,point);
                for(int i=0;i<inx;++i) val[tot+i+1]=s[i];
                son[son[root][1]][0]=build(tot+1,tot+inx),fa[son[son[root][1]][0]]=son[root][1];
                pushup(son[root][1]);
                pushup(root);
                tot+=inx;
                break;
            }
            case 'D':
            {
                scanf("%d",&inx);
                split(point+1,point+inx);
                son[son[root][1]][0]=0;
                pushup(son[root][1]);
                pushup(root);
                break;
            }
            case 'G':
            {
                scanf("%d",&inx);
                dfs(split(point+1,point+inx));
                printf("\n");
                break;
            }
            case 'P': {point--;break;}
            case 'N': {point++;break;}
        }
    }
    return 0;
}