C++ 代码
/*
top: 将编号为s的书的位置旋转到根,将左子树接到根节点的后继上,并spaly代替pushup,bottom同理。
insert:交换相邻节点的书编号对应位置、内存池位置对应的编号、节点的编号值
ask:将编号对应位置旋转到根,输出左子树大小
query:输出第k大位置的编号
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e5+10;
int n,m,idx,root,w[N],pos[N]; //pos[x]: 编号为x的书对应的splay内存池位置
//w[x]: (内存池)位置x的书的编号
struct Node{
int s[2],p,v;
int size,flag;
void init(int _v,int _p){
v=_v,p=_p;
size=1;
}
}tr[N];
void pushup(int u){
tr[u].size=tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+1;
}
// Z Z
// Y x右旋-> X
// X C A Y
// A B B C
void rotate(int x){
int y=tr[x].p,z=tr[y].p;
int ky=tr[y].s[1]==x,kz=tr[z].s[1]==y;
tr[z].s[kz]=x,tr[x].p=z;
tr[y].s[ky]=tr[x].s[ky^1],tr[tr[x].s[ky^1]].p=y;
tr[x].s[ky^1]=y,tr[y].p=x;
pushup(y),pushup(x);
}
void splay(int x,int k){
while(tr[x].p!=k){
int y=tr[x].p,z=tr[y].p;
if(z!=k)
if((tr[z].s[1]==y)^(tr[y].s[1]==x)) rotate(x);
else rotate(y);
rotate(x);
}
if(!k) root=x;
}
void tb(int s,int k){
splay(pos[s],0);
if(!tr[root].s[k]) return ;
if(!tr[root].s[!k]) {
tr[root].s[!k]=tr[root].s[k];
tr[root].s[k]=0;
return ;
}
int u=tr[root].s[!k];
while(tr[u].s[k]) u=tr[u].s[k];
int v=tr[root].s[k];
tr[v].p=u,tr[u].s[k]=v,tr[root].s[k]=0;
splay(u,0); //splay代替一条链上的pushup
}
int get_key(int k){
int u=root;
while(1){
if(k<=tr[tr[u].s[0]].size) u=tr[u].s[0];
else if(tr[tr[u].s[0]].size+1==k) return tr[u].v;
else k-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];
}
}
void build(){
for(int i=1;i<=n;i++){
int u=root;
while(tr[u].s[1]) u=tr[u].s[1];
tr[++idx].init(w[i],u),tr[u].s[1]=idx,pos[w[i]]=idx;
splay(idx,0);
}
}
void insert(int s,int t){
splay(pos[s],0);
if(!t) return ;
if(t==1){
int suc=tr[root].s[1],ps=pos[s];
while(tr[suc].s[0]) suc=tr[suc].s[0];
swap(tr[root].v,tr[suc].v);
swap(pos[w[suc]],pos[s]);
swap(w[ps],w[suc]);
}
else{
int pre=tr[root].s[0],ps=pos[s];
while(tr[pre].s[1]) pre=tr[pre].s[1];
swap(tr[root].v,tr[pre].v);
swap(pos[w[pre]],pos[s]);
swap(w[ps],w[pre]);
}
}
void ask(int s){
splay(pos[s],0);
cout<<tr[tr[root].s[0]].size<<endl;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
build();
char op[20];
while(m--){
cin>>op;
int s,t;
if(op[0]=='T'){
cin>>s;
tb(s,0);
}
else if(op[0]=='B'){
cin>>s;
tb(s,1);
}
else if(op[0]=='I'){
cin>>s>>t;
insert(s,t);
}
else if(op[0]=='A'){
cin>>s;
ask(s);
}
else{
cin>>s;
cout<<get_key(s)<<endl;
}
}
return 0;
}