学习了如何在维护序列的平衡树上查找某个数：按初始的顺序定个权值，然后每次找那个权值的DFS序即可。具体实现就是不停往上跳，然后是父亲的右儿子就加上父亲的左儿子，剩下的就是继续熟悉无旋树堆
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int num[N],val[N],siz[N],anc[N],son[N][],rnk[N];
int n,m,w,x,y,z,rd,re,tot,pos,root; char ch[];
void Pushup(int nde)
{
siz[nde]=siz[son[nde][]]+siz[son[nde][]]+;
if(son[nde][]) anc[son[nde][]]=nde;
if(son[nde][]) anc[son[nde][]]=nde;
}
int Create(int tsk)
{
siz[++tot]=;
val[tot]=tsk;
num[tsk]=tot;
rnk[tot]=rand();
return tot;
}
int Merge(int x,int y)
{
if(!x||!y) return x+y;
else if(rnk[x]<=rnk[y])
{
son[x][]=Merge(son[x][],y);
Pushup(x); return x;
}
else
{
son[y][]=Merge(x,son[y][]);
Pushup(y); return y;
}
}
void Split(int nde,int &x,int &y,int tsk)
{
if(!nde) x=y=;
else
{
if(siz[son[nde][]]<tsk)
x=nde,Split(son[nde][],son[nde][],y,tsk-siz[son[nde][]]-);
else
y=nde,Split(son[nde][],x,son[nde][],tsk);
Pushup(nde);
}
}
int Query(int nde)
{
int ret=siz[son[nde][]]+;
while(anc[nde]) {
if(nde==son[anc[nde]][])
ret+=siz[son[anc[nde]][]]+;
nde=anc[nde];
}
return ret;
}
void DFS(int nde)
{
if(son[nde][]) DFS(son[nde][]);
printf("->%d",val[nde]);
if(son[nde][]) DFS(son[nde][]);
}
int main()
{
srand();
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&rd),root=Merge(root,Create(rd));
while(m--)
{
scanf("%s%d",ch,&rd),pos=Query(num[rd]);
if(ch[]=='T')
{
Split(root,x,z,pos),Split(x,x,y,pos-);
root=Merge(Merge(y,x),z);
}
else if(ch[]=='B')
{
Split(root,x,z,pos),Split(x,x,y,pos-);
root=Merge(Merge(x,z),y);
}
else if(ch[]=='I')
{
scanf("%d",&re);
if(re==-)
{
Split(root,w,z,pos),Split(w,w,y,pos-);
Split(w,w,x,pos-); root=Merge(Merge(Merge(w,y),x),z);
}
else if(re==)
{
Split(root,y,z,pos+),Split(y,x,y,pos);
Split(x,w,x,pos-); root=Merge(Merge(Merge(w,y),x),z);
}
}
else if(ch[]=='A')
printf("%d\n",pos-);
else
{
Split(root,x,z,rd),Split(x,x,y,rd-);
printf("%d\n",val[y]);
root=Merge(Merge(x,y),z);
}
}
return ;
}