[ZJOI2006] 书架

题意

要求对一个元素互不相同的整数序列维护以下操作：

1. 把某个数放到序列开头（左端）
2. 把某个数放到序列结尾
3. 把某个数和它左边的数交换
4. 把某个数和它右边的数交换
5. 询问某一个数字在序列的位置
6. 询问在序列上某一位置的数是多少

.

分析

对于这种元素到处跑的题显然就是平衡树啦

我们维护一颗普通的 splay，然后把结点编号与元素建立相互对应的指针，这样我们就能从结点访问元素，从元素访问结点

我们维护平衡树中的最小键值 tp 和最大键值 bt

对于操作 1，相当于删除原结点，添加一个键值为 tp-1 的结点，更新指针和 tp；操作 2 同理

操作 3 就是把某结点和它的前驱结点的指针信息交换一下；操作 4 同理

操作 5 就是 rank 查询，操作 6 就是 k 小值查询

代码

#include<cstdio>
using namespace std;
const int N=2e5+5;
int n,m;

int rt,tot;
int pa[N],ch[N][2],val[N],cnt[N],sz[N];
int bk[N],nd[N];// 结点指向书；书指向结点

bool get(int u){return ch[pa[u]][1]==u;}
void pushup(int u){sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+cnt[u];}

void rotate(int u){int p=pa[u],pp=pa[p],k=get(u);
    ch[pp][get(p)]=u,pa[u]=pp;
    ch[p][k]=ch[u][k^1],pa[ch[u][k^1]]=p;
    ch[u][k^1]=p,pa[p]=u;
    pushup(p),pushup(u);
}
void splay(int u,int v){while(pa[u]!=v){int p=pa[u];
        if(pa[p]!=v)rotate(get(p)==get(u)?p:u);
        rotate(u);
    }
    if(!v)rt=u;
}
void find(int key){if(!rt)return;
    int u=rt;
    while(val[u]!=key&&ch[u][val[u]<key])u=ch[u][val[u]<key];
    splay(u,0);
}
void insert(int key){
    int u=rt,p=0;
    while(val[u]!=key&&u)p=u,u=ch[u][val[u]<key];
    if(u)++cnt[u];
    else {
        u=++tot;
        if(p)ch[p][val[p]<key]=u;
        ch[u][0]=ch[u][1]=0,pa[u]=p,val[u]=key,sz[u]=cnt[u]=1;
    }
    splay(u,0);
}
int rk(int key){find(key);
    return sz[ch[rt][0]];
}
int kth(int k){
    ++k;
    int u=rt;
    while(1){if(sz[ch[u][0]]+cnt[u]<k)k-=sz[ch[u][0]]+cnt[u],u=ch[u][1];
        else if(k<=sz[ch[u][0]])u=ch[u][0];
        else return u;
    }
}
int pre(int key){find(key);
    if(val[rt]<key)return rt;
    int u=ch[rt][0];
    while(ch[u][1])u=ch[u][1];
    return u;
}
int suc(int key){find(key);
    if(val[rt]>key)return rt;
    int u=ch[rt][1];
    while(ch[u][0])u=ch[u][0];
    return u;
}
void del(int key){int pr=pre(key),su=suc(key);
    splay(pr,0),splay(su,pr);
    int u=ch[su][0];
    if(cnt[u]>1)--cnt[u],splay(u,0);
    else ch[su][0]=0,splay(su,0);
}
int tp,bt;

int main(){scanf("%d%d",&n,&m);
    insert(1<<30),insert(-1<<30);
    for(int i=1,x;i<=n;i++){scanf("%d",&x);
        insert(i),bk[rt]=x,nd[x]=rt;
    }
    tp=1,bt=n;// 最顶上的键值
    for(int i=1,s,t;i<=m;i++){char opt[10];
        scanf("%s%d",opt,&s);
        if(opt[0]=='T')del(val[nd[s]]),insert(--tp),bk[rt]=s,nd[s]=rt;
        else if(opt[0]=='B')del(val[nd[s]]),insert(++bt),bk[rt]=s,nd[s]=rt;
        else if(opt[0]=='I'){scanf("%d",&t);
            if(t==1){int su=suc(val[nd[s]]),u=nd[s];
                nd[bk[su]]=u,bk[u]=bk[su];
                bk[su]=s,nd[s]=su;
            }
            else if(t==-1){int pr=pre(val[nd[s]]),u=nd[s];
                nd[bk[pr]]=u,bk[u]=bk[pr];
                bk[pr]=s,nd[s]=pr;
            }
        }
        else if(opt[0]=='A'){printf("%d\n",rk(val[nd[s]])-1);}
        else if(opt[0]=='Q'){printf("%d\n",bk[kth(s)]);}
    }
    return 0;
}

Extra

调试的时候写了一个基于 dot 的画图函数，用来画平衡树的，貌似很好用？

#include<string>
#include<fstream>
int draw_times;
ofstream dot;
void rec_draw(int u){if(ch[u][0])dot<<u<<"->"<<ch[u][0]<<endl,rec_draw(ch[u][0]);
    if(ch[u][1])dot<<u<<"->"<<ch[u][1]<<endl,rec_draw(ch[u][1]);
    dot<<u<<"[label=\""<<u<<"\\n[sz]"<<sz[u]<<"\"];\n";
}
void draw(string info){const string name="[pic]";
    ++draw_times;
    dot.open("tmpdot.dot");
    dot<<"digraph wll{\n";
    dot<<"graph [nodesep=1, ranksep=2, fontsize=24, fontname=\"Microsoft Yahei\", label=\""<<name<<tot<<info<<"\"];\n";
    dot<<"node [style=filled,shape=circle];\n";
    rec_draw(rt);
    dot<<"}\n";
    dot.close();
    string pre(draw_times>99?0:(draw_times>9?1:2),'0');
    system(("dot tmpdot.dot -Tpng -o"+name+pre+to_string(draw_times)+".png").c_str());
}