链接：https://www.luogu.org/problemnew/show/P2596
题解：
写了两天的平衡树终于大概弄好了所有模板（模板不熟写错debug真是要死）
对于放在头尾，只需要删除，再在头/尾插入就可以了
对于交换，就交换一下映射
代码：
#include <bits/stdc++.h>
#define maxn 100000
using namespace std;
int n,m,data[maxn],count2[maxn],leftson[maxn],rightson[maxn],fa[maxn],a[maxn],
point[maxn],num,root;
void updata(int x)
{
count2[x]=count2[leftson[x]]+count2[rightson[x]]+;
}
void rotate(int x,int y)
{
int father=fa[x];
if (y==)
{
rightson[father]=leftson[x];
if (leftson[x]) fa[leftson[x]]=father;
} else
{
leftson[father]=rightson[x];
if (rightson[x]) fa[rightson[x]]=father;
}
fa[x]=fa[father];
if (fa[father])
{
if (leftson[fa[father]]==father)
leftson[fa[father]]=x;
else rightson[fa[father]]=x;
}
fa[father]=x;
if (y==) leftson[x]=father; else rightson[x]=father;
updata(father); updata(x);
}
void splay(int x,int goal)
{
if (x==root) return;
int father=fa[x];
while (father!=goal)
{
if (fa[father]==goal)
{
if (x==leftson[father]) rotate(x,); else rotate(x,);
} else
{
if (father==leftson[fa[father]])
{
if (x==leftson[father]) rotate(father,),rotate(x,);
else rotate(x,),rotate(x,);
} else
{
if (x==rightson[father]) rotate(father,),rotate(x,);
else rotate(x,),rotate(x,);
}
}
father=fa[x];
}
if (goal==) root=x;
}
#define mid (h+t)/2
void build(int h,int t,int father,bool x,int a[maxn])
{
count2[++num]=; data[num]=a[mid]; fa[num]=father;
point[a[mid]]=num;
if (father)
{
if (x==) leftson[father]=num; else rightson[father]=num;
}
int tmp=num;
if (h<mid) build(h,mid-,tmp,,a);
if (mid<t) build(mid+,t,tmp,,a);
updata(tmp);
}
int search(int goal)
{
int x=root,cnt=;
while (x)
{
if (cnt+count2[leftson[x]]==goal) return(x);
if (count2[leftson[x]]+cnt<goal)
{
cnt+=count2[leftson[x]]+; x=rightson[x];
} else
{
x=leftson[x];
}
}
}
void delete1()
{
int x=leftson[root];
if (x==)
{
root=rightson[root]; fa[root]=; return;
}
while (rightson[x]) x=rightson[x];
splay(x,root);
rightson[x]=rightson[root];
if (rightson[root]) fa[rightson[root]]=x;
updata(x);
root=x; fa[x]=;
}
void insert1(int x)
{
int y=root;
while (leftson[y]) count2[y]++,y=leftson[y]; count2[y]++;
leftson[y]=x; fa[x]=y; leftson[x]=; rightson[x]=; count2[x]=;
}
void insert2(int x)
{
int y=root;
while (rightson[y]) count2[y]++,y=rightson[y]; count2[y]++;
rightson[y]=x; fa[x]=y; rightson[x]=; leftson[x]=; count2[x]=;
}
void print(int x)
{
if (leftson[x]) print(leftson[x]);
cout<<data[x]<<" ";
if (rightson[x]) print(rightson[x]);
}
char c[];
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
cin>>n>>m;
for (int i=;i<=n;i++)
{
cin>>a[i];
}
build(,n,,,a); root=;
for (int i=;i<=m;i++)
{
// print(root); cout<<i-1<<endl;
cin>>c; int d,e;
if (c[]=='T')
{
cin>>d; int x=point[d]; splay(x,);
delete1(); insert1(x);
}
if (c[]=='B')
{
cin>>d; int x=point[d]; splay(x,);
delete1();
insert2(x);
}
if (c[]=='I')
{
cin>>d>>e;
if (e!=)
{
int x1=point[d]; splay(x1,);
int x2=search(count2[leftson[x1]]++e);
swap(point[d],point[data[x2]]);
swap(data[x2],data[x1]);
}
}
if (c[]=='A')
{
cin>>d; int x=point[d];
splay(x,);
cout<<count2[leftson[x]]<<endl;
}
if (c[]=='Q')
{
cin>>d; int x=search(d);
cout<<data[x]<<endl;
}
}
}