单点插入删除以及求前缀
#include#include #include using namespace std;const int M=100055,inf=1000000000;int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f;}int n,m,root;int c[M][2],size[M],fa[M],v[M],pos[M];void up(int k){size[k]=size[c[k][0]]+size[c[k][1]]+1;}void rotate(int x,int& k){ int y=fa[x],z=fa[y],l=0,r=1; if(c[y][1]==x) l=1,r=0; if(y==k) k=x; else{ if(c[z][0]==y) c[z][0]=x; else c[z][1]=x;} fa[y]=x; fa[x]=z; fa[c[x][r]]=y; c[y][l]=c[x][r]; c[x][r]=y; up(y); up(x);}void splay(int x,int& k){ while(x!=k){ int y=fa[x],z=fa[y]; if(y!=k){ if(c[z][0]==y^c[y][0]==x) rotate(y,k); else rotate(x,k); } rotate(x,k); }}int find(int x,int rank){ int l=c[x][0],r=c[x][1]; if(size[l]+1==rank) return x; else if(size[l]>=rank) return find(l,rank); else return find(r,rank-size[l]-1);}int build(int l,int r){ if(l>r) return 0; int m=(l+r)>>1; c[m][0]=build(l,m-1); c[m][1]=build(m+1,r); for(int i=0;i<2;i++) if(c[m][i]) fa[c[m][i]]=m; up(m); return m;}void del(int k){ int x,y,z; x=find(root,k-1); y=find(root,k+1); splay(x,root); splay(y,c[x][1]); z=c[y][0]; c[y][0]=0; size[z]=fa[z]=0; up(y); up(x);}void move(int k,int w){ int x,y,z=pos[k],rank; splay(z,root); rank=size[c[z][0]]+1; del(rank); if(w==-inf) x=find(root,1),y=find(root,2); else if(w==inf) x=find(root,n),y=find(root,n+1); else x=find(root,rank+w-1),y=find(root,rank+w); splay(x,root); splay(y,c[x][1]); size[z]=1; fa[z]=y; c[y][0]=z; up(y); up(x);}int main(){ int k,T; n=read(); m=read(); for(int i=2;i<=n+1;i++) v[i]=read(),pos[v[i]]=i; root=build(1,n+2); char ch[15]; while(m--){ scanf("%s",ch); k=read(); if(ch[0]=='T') move(k,-inf); if(ch[0]=='B') move(k,inf); if(ch[0]=='I') T=read(),move(k,T); if(ch[0]=='A') splay(pos[k],root),printf("%d\n",size[c[pos[k]][0]]-1); if(ch[0]=='Q') T=find(root,k+1),printf("%d\n",v[T]); } return 0;}