题意
要求对一个元素互不相同的整数序列维护以下操作:
- 把某个数放到序列开头(左端)
- 把某个数放到序列结尾
- 把某个数和它左边的数交换
- 把某个数和它右边的数交换
- 询问某一个数字在序列的位置
- 询问在序列上某一位置的数是多少
.
分析
对于这种元素到处跑的题显然就是平衡树啦
我们维护一颗普通的 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());
}