[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());
}

  转载请注明: Sshwy's Blog [ZJOI2006] 书架

 上一篇
Splay 进阶 Splay 进阶
前言splay 初步 里面提到了 splay 的拓展性 其实 splay 不只是用于维护二叉搜索树,有时候也会脱离二叉搜索树的范畴 Splay 维护区间信息区间信息通常可以用线段树或者树状数组维护,不过不可忽略的是 Splay 也可以维护
2019.01.18
下一篇 
生成树算法 生成树算法
补一篇生成树(Spanning Tree)的文章 生成树一个比较鬼扯的定义:对于一个图 ,它的生成树是一个连通子图 ,其中 。 最小生成树对于一个加权图 G,最小生成树(M
2019.01.17
  目录