\(\color{purple}\text{P2596 [ZJOI2006]书架}\)
解题方法
考虑使用 \(\text{FHQ}\) 平衡树 ，我们只使用编号，而不使用权值，平衡树上的先序遍历即为书的放置顺序。
- \(\text{Query}\) ：这是最简单的操作，直接查询即可。
- \(\text{Ask}\)：本题的核心，我们知道编号，因为没有权值，没法从根往下找到询问点，如果强制设权值会很麻烦。正难则反，既然我们知道询问点的编号，不如从询问点向上走回根，这个操作需要我们维护每个节点的父亲。（记得每次树改变时把根的父亲设为 \(0\) ）
- \(\text{Bottom/Top/Insert}\) 既然已经有了 \(Ask\) ，我们可以直接通过编号找到排名，继而分裂出需要改变的点，剩下的就是重新组合。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+110;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
int n,m,rl[N],fx[N];
struct FHQ{
int rt,x,y,z,cnt,phi;
int ls[N],rs[N],rad[N],sze[N];
int fa[N];
void pushup(int u){sze[u]=sze[ls[u]]+sze[rs[u]]+1;return;}
int newnode(){
rad[++cnt]=rand();
sze[cnt]=1;
return cnt;
}
void split(int u,int k,int &x,int &y,int fax,int fay){
if(!u)x=0,y=0;
else{
if(k>sze[ls[u]]){
x=u;fa[u]=fax;
split(rs[u],k-sze[ls[u]]-1,rs[u],y,u,fay);
}
else{
y=u;fa[u]=fay;
split(ls[u],k,x,ls[u],fax,u);
}
pushup(u);
}
return;
}
int merge(int A,int B){
if(!A || !B)return A+B;
if(rad[A]<rad[B]){rs[A]=merge(rs[A],B);fa[rs[A]]=A;pushup(A);return A;}
else {ls[B]=merge(A,ls[B]);fa[ls[B]]=B;pushup(B);return B;}
}
void insert(){rt=merge(rt,newnode());return;}
int Query(int k){
split(rt,k,x,z,0,0);
split(x,k-1,x,y,fa[x],fa[y]);
int tmp=y;rt=merge(merge(x,y),z);fa[rt]=0;
return tmp;
}
int ask(int x,int fr){
if(x==0)return 0;
if(fr==ls[x])return ask(fa[x],x);
else return ask(fa[x],x)+sze[ls[x]]+1;
}
int Ask(int x){return ask(fa[x],x)+sze[ls[x]];}
void top(int k){
split(rt,k-1,x,y,fa[x],fa[y]);
split(y,1,y,z,fa[y],fa[z]);
rt=merge(y,merge(x,z));fa[rt]=0;
}
void bottom(int k){
split(rt,k-1,x,y,fa[x],fa[y]);
split(y,1,y,z,fa[y],fa[z]);
rt=merge(merge(x,z),y);fa[rt]=0;
}
void sap(int k,int t){
if(t==-1){
split(rt,k-2,x,y,fa[x],fa[y]);
split(y,1,y,z,fa[y],fa[z]);
split(z,1,z,phi,fa[z],fa[phi]);
rt=merge(merge(x,z),merge(y,phi));fa[rt]=0;
}
if(t==1){
split(rt,k-1,x,y,fa[x],fa[y]);
split(y,1,y,z,fa[y],fa[z]);
split(z,1,z,phi,fa[z],fa[phi]);
rt=merge(merge(x,z),merge(y,phi));fa[rt]=0;
}
return;
}
void sd(int u){
if(!u)return;
cout<<u<<" "<<sze[u]<<" "<<ls[u]<<" "<<rs[u]<<" "<<fa[u]<<endl;
sd(ls[u]);
sd(rs[u]);
}
void Bark(){
printf("-----------HYC is here-----------\n");
sd(rt);
printf("-----------HYC has gone-----------\n");
}
}T;
int main(){
srand(20230502);
n=read(),m=read();
for(int i=1;i<=n;i++)rl[i]=read(),fx[rl[i]]=i;//树编号-》实际编号；实际编号-》树编号
for(int i=1;i<=n;i++)T.insert();
// T.Bark();
for(int i=1;i<=m;i++){
char opt[10];scanf("%s",opt);
if(opt[0]=='Q'){int k=read();printf("%d\n",rl[T.Query(k)]);}
if(opt[0]=='A'){int x=read();printf("%d\n",T.Ask(fx[x]));}
if(opt[0]=='T'){int x=read();T.top(T.Ask(fx[x])+1);}
if(opt[0]=='B'){int x=read();T.bottom(T.Ask(fx[x])+1);}
if(opt[0]=='I'){int x=read(),t=read();T.sap(T.Ask(fx[x])+1,t);}
// T.Bark();
}
return 0;
}