题解：记录每本书对应的节点编号
普通fhq_treap无法查询一个权值的排名，所以在普通fhq_treap上多记录每个节点的父亲（可加在pushup函数中），
查询时从该节点开始逐步往上跳，记录答案。
其他操作都依附在该排名上。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
using namespace std;
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=(8e4)+;
int N,M,lc[maxn],rc[maxn],val[maxn],pr[maxn],tot=,siz[maxn];
int u,rt=,s,t,x,y,z,id[maxn],fa[maxn],k;
//id[i]表示编号为i的书所在的节点编号
char o[];
inline int New_node(int x){
val[++tot]=x;
siz[tot]=;
pr[tot]=rand();
return tot;
}
inline void Pushup(int x){
siz[x]=siz[lc[x]]+siz[rc[x]]+;
fa[lc[x]]=fa[rc[x]]=x;
return;
}
inline void Split(int now,int k,int &x,int &y){
if(!now){
x=y=fa[x]=fa[y]=;
return;
}
if(siz[lc[now]]+<=k){
x=now;
Split(rc[now],k-siz[lc[now]]-,rc[now],y);
}
else {
y=now;
Split(lc[now],k,x,lc[now]);
}
Pushup(now);
return;
}
inline int Merge(int x,int y){
if(!x||!y){
fa[x]=fa[y]=x+y;
return x+y;
}
if(pr[x]<pr[y]){
rc[x]=Merge(rc[x],y);
Pushup(x);
return x;
}
else{
lc[y]=Merge(x,lc[y]);
Pushup(y);
return y;
}
}
inline int Find(int x){//寻找x节点上有多少书
int sum=;
sum+=siz[lc[x]];
while(x!=rt){
if(rc[fa[x]]==x)sum+=siz[lc[fa[x]]]+;
x=fa[x];
}
return sum;
}
inline int Query(int k){
int now=rt;
while(now){
if(k<=siz[lc[now]])now=lc[now];
else if(k==siz[lc[now]]+)return now;
else k-=siz[lc[now]]+,now=rc[now];
}
return ;
}
int main(){
srand();
N=rd();M=rd();
for(int i=;i<=N;i++){
u=rd();
rt=Merge(rt,id[u]=New_node(u));
}
while(M--){
scanf("%s",o); s=rd();
if(o[]=='T'){
k=Find(id[s]);
Split(rt,k+,x,z);
Split(x,k,x,y);
rt=Merge(Merge(x,Merge(lc[y],rc[y])),z);
rt=Merge(id[s],rt);
}
else if(o[]=='B'){
k=Find(id[s]);
Split(rt,k+,x,z);
Split(x,k,x,y);
rt=Merge(Merge(x,Merge(lc[y],rc[y])),z);
rt=Merge(rt,id[s]);
}
else if(o[]=='I'){
t=rd();
k=Find(id[s]);
Split(rt,k+,x,z);
Split(x,k,x,y);
rt=Merge(Merge(x,Merge(lc[y],rc[y])),z);
Split(rt,k+t,x,y);
rt=Merge(Merge(x,id[s]),y);
}
else if(o[]=='A'){
printf("%d\n",Find(id[s]));
}
else {//Q
printf("%d\n",val[Query(s)]);
}
}
return ;
}
By:AlenaNuna