链接：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]]+1; } void rotate(int x,int y) { int father=fa[x]; if (y==1) { 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==1) 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,2); else rotate(x,1); } else { if (father==leftson[fa[father]]) { if (x==leftson[father]) rotate(father,2),rotate(x,2); else rotate(x,1),rotate(x,2); } else { if (x==rightson[father]) rotate(father,1),rotate(x,1); else rotate(x,2),rotate(x,1); } } father=fa[x]; } if (goal==0) root=x; } #define mid (h+t)/2 void build(int h,int t,int father,bool x,int a[maxn]) { count2[++num]=1; data[num]=a[mid]; fa[num]=father; point[a[mid]]=num; if (father) { if (x==1) leftson[father]=num; else rightson[father]=num; } int tmp=num; if (h<mid) build(h,mid-1,tmp,1,a); if (mid<t) build(mid+1,t,tmp,0,a); updata(tmp); } int search(int goal) { int x=root,cnt=1; while (x) { if (cnt+count2[leftson[x]]==goal) return(x); if (count2[leftson[x]]+cnt<goal) { cnt+=count2[leftson[x]]+1; x=rightson[x]; } else { x=leftson[x]; } } } void delete1() { int x=leftson[root]; if (x==0) { root=rightson[root]; fa[root]=0; 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]=0; } 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]=0; rightson[x]=0; count2[x]=1; } 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]=0; leftson[x]=0; count2[x]=1; } void print(int x) { if (leftson[x]) print(leftson[x]); cout<<data[x]<<" "; if (rightson[x]) print(rightson[x]); } char c[100]; int main() { freopen("noip.in","r",stdin); freopen("noip.out","w",stdout); cin>>n>>m; for (int i=1;i<=n;i++) { cin>>a[i]; } build(1,n,0,0,a); root=1; for (int i=1;i<=m;i++) { // print(root); cout<<i-1<<endl; cin>>c; int d,e; if (c[0]=='T') { cin>>d; int x=point[d]; splay(x,0); delete1(); insert1(x); } if (c[0]=='B') { cin>>d; int x=point[d]; splay(x,0); delete1(); insert2(x); } if (c[0]=='I') { cin>>d>>e; if (e!=0) { int x1=point[d]; splay(x1,0); int x2=search(count2[leftson[x1]]+1+e); swap(point[d],point[data[x2]]); swap(data[x2],data[x1]); } } if (c[0]=='A') { cin>>d; int x=point[d]; splay(x,0); cout<<count2[leftson[x]]<<endl; } if (c[0]=='Q') { cin>>d; int x=search(d); cout<<data[x]<<endl; } } }