- 注意书先要取出然后才能放回(先删再插)
- 注意在排名分裂fhq中,需要一个id数组记录编号为id的点在树中的编号,其实就是提问和树上问题转化
- 排名分裂线段树特色寻求排名的方法
int get_k(int root,int k)
{
int u=k;
int res= t(u).siz -trs(u).siz;
while (u!=root)
{
if(u==rs(t(u).p)) res+= (t(t(u).p).siz -t(u).siz);
u=t(u).p;
}
return res;
}
#include<bits/stdc++.h>
#define ls(x) tr[x].l
#define rs(x) tr[x].r
#define t(x) tr[x]
#define tls(x) t(ls(x))
#define trs(x) t(rs(x))
using namespace std;
const int N=8e4+9 ;
int x,y,z,n,m;
int tot;
int root;
int id[N];
struct node
{
int l,r,p;
int key;
int siz;
int v;
void init (int val)
{
l=r= 0; siz = 1;
p=0;
v= val; key= rand();
}
}tr[N*2];
void up(int x)
{
t(x).siz= trs(x).siz+tls(x).siz + 1;
tls(x).p=trs(x).p=x;
}
void split (int p,int k,int &x,int &y)
{
if(p==0)
{
x=y= 0;
return;
}
if(tls(p).siz<k)
{
x=p;
split(rs(x),k-tls(p).siz-1,rs(x),y);
up(x);
}
else
{
y=p;
split(ls(y),k,x,ls(y));
up(y);
}
}
int merge (int x,int y)
{
if(x==0||y==0)return x+y;
if(t(x).key<t(y).key)
{
rs(x)=merge(rs(x),y);
up(x);
return x;
}
else
{
ls(y)= merge(x,ls(y));
up(y);
return y;
}
}
int new_node (int val)
{
t(++tot).init(val);
return tot;
}
int get_k(int root,int k)
{
int u=k;
int res= t(u).siz -trs(u).siz;
while (u!=root)
{
if(u==rs(t(u).p)) res+= (t(t(u).p).siz -t(u).siz);
u=t(u).p;
}
return res;
}
int get_v(int root,int k)
{
int u=root;
while (u)
{
if(tls(u).siz >= k)u=ls(u);
else if(tls(u).siz+1==k)return t(u).v;
else k-=tls(u).siz+1, u=rs(u);
}
}
void out(int x)
{
if(ls(x))out(ls(x));
cout<<t(x).v<<" ";
if(rs(x))out(rs(x));
}
signed main()
{
int k,t;
int last =0;
scanf("%d", &n);
scanf("%d", &m);
for(int i=1;i<=n;i++)
{
scanf("%d",&k);
id[k]=new_node(k);
root=merge(root,id[k]);
}
while(m--)
{
char op[20];
scanf("%s",op);
scanf("%d",&k);
if(op[0]=='T')
{
int pos= get_k(root,id[k]);
split(root,pos,x,z);
split(x,pos-1,x,y);
root=merge(merge(id[k],x),z);
}
else if(op[0]=='B')
{
int pos= get_k(root,id[k]);
split(root,pos,x,z);
split(x,pos-1,x,y);
root=merge(merge(x,z),id[k]);
}
else if(op[0]=='I')
{
scanf("%d",&t);
int pos = get_k(root,id[k]);
split(root,pos,x,z);
split(x,pos-1,x,y);
root=merge(x,z);
pos+=t;
split(root,pos-1,x,z);
root = merge(merge(x,id[k]),z);
}
else if(op[0]=='A')last = get_k(root,id[k])-1;
else if(op[0]=='Q')last = get_v(root,k);
if (op[0]=='A'||op[0]=='Q')printf("%d\n",last);
}
return 0;
}