作者存档：edward_mj

【算法分析】

鉴于zyylhappy提到这题，大年初一的凌晨心血来潮爬起来，就把它做了。

网上大部分看到都是块状链表或者说beyondvoid大神的splay。

但是我不会splay，块状链表觉得太不和谐了，于是我果断就拿起了具有我们广东特色的数据结构——陈启峰树(SBT)。虽然说着比较牵强。。。

然后这题嘛，我的思路就是把字符串拆成字符，按位置前后作为key值大小，插入我们可爱的平衡树之中。

虽然我的程序没有定义这个位置，但是这是可以体现出来的。

我们注意到旋转的性质，旋转以后，整体是排序二叉树这一性质不会被破坏（废话）

所以我们可以无所顾忌的用SBT去弄到他平衡。

但是我刚写出来的时候一用cena测试。。。悲剧，栈溢出

。。。偶就是为了栈不溢出才学的C++，你现在告诉我你也溢出了

分析一下，我发现我写的时候是找到那个光标位置的下一个插入点的时候，一口气插完了整个字符串，

然后在递归回来修复，这样的话，栈就需要搞到一次插入的字符串长度的大小。而据我不完全统计，它一次插入的字符串有时候甚至长度超10^6（这不是猥琐是什么？）。

偶就改成一个一个字符地插入SBT之中。但是这样的话，插入一个字符串的代价变成O(LEN*lgSUM)。SUM是全部字符的个数。

于是，很果断地TLE，几乎全部跑了6S多。。。（在我这特别残破的机器上，估计是beyondvoid大牛2001买的电脑的1/3的运算速度。。。据beyondvoid大牛说我应该是运行环境有问题，而我悲剧地不会改）

额。然后我想放弃了，但是突然有想到直接插入那颗这么大的平衡树的话，那个lg会变得比较大，而我现在就是被常数卡住了。

于是我就是采取的这样的方法来解决insert操作：先建一颗SBT，然后在找到光标，把新建的SBT的树根拼在那上面。然后这样插入一个长度为LEN的字符串，复杂度会变成O(LEN*lgLEN)

于是高高兴兴地一测，全部4s多，然后我找到时间限制一看，2~4s。于是当场纠结在那。。。我想，如果是beyondvoid的电脑，我是能过的吧

不过我喜欢追求完美。。。所以想搞到在自己这台垃圾机器上也能AC，所以继续优化。

由于上一次注意到他一次插入的字符串长度可能超10^6，于是就觉得肯定是新建SBT的时候O(LEN*lgLEN)的复杂度还是不够快，毕竟他来多几次10^6的话，正常的SBT都要完蛋。。。

于是苦思冥想之后，发现一种新的构建方法——二分区间。

因为是字符串，而且是以先后顺序作为平衡二叉树的关键字，所以我建SBT的话，会每次都找到向右的最长链，然后插入的新的位置当中。如果是有这个单调性的话，那么就可以考虑二分了。

二分构建的话，这棵树会直接达到最平衡，然后插入的复杂度就是O(LEN)！

扯远了。。。先来说说怎么二分。

就是每次把字符串中间的那个字符抽出来放中间，然后左边的放左边去，右边的右边去。

就像这样：

void build(int &p,int l,int r){
    if (l>r) return;
    int mid=(l+r)/2;
    tot++;
    p=tot;
    tr[p].l=0;
    tr[p].r=0;
    tr[p].key=str[mid];
    build(tr[p].l,l,mid-1);
    build(tr[p].r,mid+1,r);
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}   

这样构建以后，一个完全平衡的二叉树插入到SBT某个关键位置的话，旋转次数大大减少。

一测，果然AC!

【其它】经测试，beyondvoid的splay在我这台机器上用了6.22s通过所有的测试数据，我的总共用了5.00s

而我这个长度也算比较短。。。160行，beyondvoid的splay上220行吧。。。块状链表不知。

【CODE】

#include const int N=1025*1025*10;
struct {int l,r,s;char key;}tr[N];
char op[20],str[N];
int tot,root,gb,len,done,nowi,troot;

inline void left(int &k){
    int p=tr[k].r;
    tr[k].r=tr[p].l;
    tr[p].l=k;
    tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+1;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    k=p;
}

inline void right(int &k){
    int p=tr[k].l;
    tr[k].l=tr[p].r;
    tr[p].r=k;
    tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+1;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    k=p;
}

inline void repair(int &k){
    bool flag=false;
    if (tr[tr[tr[k].l].l].s>tr[tr[k].r].s){
        right(k);
        flag=true;
    }else
    if (tr[tr[tr[k].l].r].s>tr[tr[k].r].s){
        left(tr[k].l);
        right(k);
        flag=true;
    }else
    if (tr[tr[tr[k].r].r].s>tr[tr[k].l].s){
        left(k);
        flag=true;
    }else
    if (tr[tr[tr[k].r].l].s>tr[tr[k].l].s){
        right(tr[k].r);
        left(k);
        flag=true;
    }
    if (flag){
        repair(tr[k].l);
        repair(tr[k].r);
        repair(k);
    }
}

inline void ins(int &p){
    if (p==0) p=troot;
    else
    if (tr[tr[p].l].s+done+1>gb) ins(tr[p].l);
    else{
        done+=tr[tr[p].l].s+1;
        ins(tr[p].r);
    }
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    repair(p);
}

inline char findr(int &p){
    tr[p].s–;
    if (tr[p].r==0){
        char tmp=tr[p].key;
        p=tr[p].l;
        return tmp;
    }
    else return findr(tr[p].r);
}

inline void del(int &p){
     if (p==0 || done>gb+len || done+tr[p].s<=gb) return;
     bool flag=false;
     int td=done+tr[tr[p].l].s+1;
     if (td>gb && td<=gb+len) flag=true;
     if (td-1>gb) del(tr[p].l);
     done=td;
     del(tr[p].r);
     if (flag)
        if (!tr[p].l || !tr[p].r) p=tr[p].l+tr[p].r;
                             else tr[p].key=findr(tr[p].l);
    if (p!=0) tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

inline void solve(int p){
    if (p==0 || done>gb+len) return;
    bool flag=false; int td=done;
    if (tr[tr[p].l].s+done+1>gb && tr[tr[p].l].s+done+1<=gb+len) flag=true;
    if (tr[tr[p].l].s+done>gb) solve(tr[p].l);
    if (flag) printf("%c",tr[p].key);
    done=td+tr[tr[p].l].s+1;
    solve(tr[p].r);
}

inline void Move(){scanf("%d",&gb);}
inline void Next(){if (gbinline void Prev(){if (gb>0) gb–;}

inline void build(int &p,int l,int r){
    if (l>r) return;
    int mid=(l+r)/2;
    tot++;
    p=tot;
    tr[p].l=0;
    tr[p].r=0;
    tr[p].key=str[mid];
    build(tr[p].l,l,mid-1);
    build(tr[p].r,mid+1,r);
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}   

inline void Ins(){
    scanf("%d",&len);
    char ch;
    for (int i=0;i        ch=getchar();
        while (ch==’n’) ch=getchar();
        str[i]=ch;
    }
    troot=0;
    build(troot,0,len-1);
    done=0;
    ins(root);
}

inline void Del(){
    scanf("%d",&len);
    done=0;
    del(root);
}

inline void Get(){
    scanf("%d",&len);
    done=0;
    solve(root);
    printf("n");
}

int main(){
    freopen("editor.in","r",stdin);
    freopen("editor.out","w",stdout);
    int tmp;
    scanf("%d",&tmp);
    for (int i=1;i<=tmp;i++){
        scanf("%s",&op);
        switch (op[0]){
            case ‘M’:Move(); break;
            case ‘I’:Ins(); break;
            case ‘D’:Del(); break;
            case ‘N’:Next(); break;
            case ‘P’:Prev(); break;
            case ‘G’:Get(); break;
        }
    }
}