这一题这个萌新的思路好像很奇怪。。。

思路是先将每个书的编号与位置绑定，将位置当成权值，然后用fhq treap

置顶/置底操作就是先删除再以最小/最大的权值插入。每个插入的位置中间会有 $80000$ 个空隙。

Insert操作则是先删除，将准备插入的位置设为 $i$ ，再将新数插到这个 $i-1$ 与 $i$ 的空隙里。

代码：

#include<iostream>
#include<cstdio>
#include<random>
#include<ctime>
#define int long long
using namespace std;
mt19937 rnd(time(0));
struct node
{
	int val,l,r,siz,key,id;
}fhq[160001];
int n,m,cnt,smax,smin,a[160001];
char op[10];
int ins(int nw,int val)
{
	fhq[++cnt].val=val;
	fhq[cnt].key=rnd();
	fhq[cnt].siz=1;
	fhq[cnt].id=nw;
	return cnt;
}
void upd(int nw)
{
	fhq[nw].siz=fhq[fhq[nw].l].siz+fhq[fhq[nw].r].siz+1;
}
void spl(int nw,int val,int &x,int &y)
{
	if(!nw) x=y=0;
	else
	{
		if(fhq[nw].val<=val)
		{
			x=nw;
			spl(fhq[nw].r,val,fhq[nw].r,y);
		}else
		{
			y=nw;
			spl(fhq[nw].l,val,x,fhq[nw].l);
		}
		upd(nw);
	}
}
int mer(int x,int y)
{
	if(!x||!y) return x+y;
	if(fhq[x].key<fhq[y].key)
	{
		fhq[x].r=mer(fhq[x].r,y);
		upd(x);
		return x;
	}else
	{
		fhq[y].l=mer(x,fhq[y].l);
		upd(y);
		return y;
	}
}
int x,y,z,root;
void inser(int id,int val)
{
	a[id]=val;
	spl(root,val,x,y);
	root=mer(mer(x,ins(id,val)),y);
}
void del(int val)
{
	spl(root,val,x,z);
	spl(x,val-1,x,y);
	y=mer(fhq[y].l,fhq[y].r);
	root=mer(mer(x,y),z);
}
int rnk(int val)
{
	spl(root,val-1,x,y);
	int ans=fhq[x].siz+1;
	root=mer(x,y);
	return ans;
}
int valu(int rnk)
{
	int nw=root;
	while(nw)
	{
		if(fhq[fhq[nw].l].siz+1==rnk) break;
		else if(fhq[fhq[nw].l].siz>=rnk) nw=fhq[nw].l;
		else
		{
			rnk-=fhq[fhq[nw].l].siz+1;
			nw=fhq[nw].r;
		}
	}
	return nw;
}
//void ccout(int nw,int fa)
//{
//	if(!nw) return;
//	cout<<nw<<" "<<fa<<" "<<fhq[nw].val<<" "<<fhq[nw].id<<endl;
//	ccout(fhq[nw].l,nw);
//	ccout(fhq[nw].r,nw);
//}
signed main()
{
	scanf("%lld%lld",&n,&m);
	smax=n+1;
	smin=-1;
	for(int i=1;i<=n;i++) 
	{
		int x;
		scanf("%lld",&x);
		inser(x,i*80000);
	}
//	ccout(root,0);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",op+1);
		int s;
		scanf("%lld",&s);
//		ccout(root,0);
		if(op[1]=='T')
		{
			del(a[s]);
			inser(s,smin*80000);
			smin--;
		}else if(op[1]=='B')
		{
			del(a[s]);
			inser(s,smax*80000);
			smax++;
		}else if(op[1]=='I')
		{
			int t;
			scanf("%lld",&t);
			int nwrk=rnk(a[s]);
//			cout<<nwrk<<" "<<nwrk+t<<endl;
			nwrk+=t;
			nwrk--;
			int val=fhq[valu(nwrk)].val;
//			cout<<nwrk<<" "<<valu(nwrk)<<endl;
			del(a[s]);
			inser(s,val+1);
		}else if(op[1]=='A')
		{
//			cout<<n<<"gxrh"<<" "<<rnk(a[s])<<endl;
			printf("%lld\n",rnk(a[s])-1);
		}else
		{
			printf("%lld\n",fhq[valu(s)].id);
		}
	}
	return 0;
}