题目大意：……自己看懒得打了
非常裸的Splay 首先开一个指针数组记录每一个值代表的节点 然后就能找到某本书在序列中的什么位置了
总感觉这题能够不用Splay的说……一定是我的错觉
例子中竟然尼玛有中文字符……坑爆了
#include#include #include #include #define M 80800using namespace std;struct abcd{ abcd *fa,*ls,*rs; int num,size; abcd(int x); void Push_Up();}*null=new abcd(0),*tree[M],*root;int n,m,a[M];abcd :: abcd(int x){ fa=ls=rs=null; num=x;size=x?1:0;}void abcd :: Push_Up(){ size = ls->size + rs->size + 1;}void Zig(abcd *x){ abcd *y=x->fa; y->ls=x->rs; x->rs->fa=y; x->rs=y; x->fa=y->fa; if(y==y->fa->ls) y->fa->ls=x; else if(y==y->fa->rs) y->fa->rs=x; y->fa=x; if(y==root) root=x; y->Push_Up();}void Zag(abcd *x){ abcd *y=x->fa; y->rs=x->ls; x->ls->fa=y; x->ls=y; x->fa=y->fa; if(y==y->fa->ls) y->fa->ls=x; else if(y==y->fa->rs) y->fa->rs=x; y->fa=x; if(y==root) root=x; y->Push_Up();}void Splay(abcd *x,abcd *tar){ while(1) { abcd *y=x->fa,*z=y->fa; if(y==tar) break; if(z==tar) { if(x==y->ls) Zig(x); else Zag(x); break; } if(x==y->ls) { if(y==z->ls) Zig(y); Zig(x); } else { if(y==z->rs) Zag(y); Zag(x); } } x->Push_Up();}void Find(abcd *x,int y,abcd *z){ while(1) { int temp=x->ls->size; if(y<=temp) x=x->ls; else { y-=temp; if(y==1) break; y--; x=x->rs; } } Splay(x,z);}abcd* Build_Tree(int l,int r){ int mid=l+r>>1; if(l>r) return null; abcd *x=tree[a[mid]]; x->ls=Build_Tree(l,mid-1); x->rs=Build_Tree(mid+1,r); x->ls->fa=x->rs->fa=x; return x->Push_Up(),x;}void Initialize(){ root=new abcd(19980402); root->rs=new abcd(19980402); root->rs->ls=Build_Tree(1,n); root->rs->ls->fa=root->rs; root->rs->Push_Up(); root->rs->fa=root; root->Push_Up();}int Get_Rank(abcd *x){ int re=x->ls->size; for(;x!=root;x=x->fa) if(x==x->fa->rs) re+=x->fa->ls->size+1; return re;}void Insert(abcd *x,int y){ Find(root,y,null); Find(root,y+1,root); root->rs->ls=x; x->fa=root->rs; root->rs->Push_Up(); root->Push_Up();}void Delete(int x){ Find(root,x,null); Find(root,x+2,root); root->rs->ls=null; root->rs->Push_Up(); root->Push_Up();}void Top(){ int x;scanf("%d",&x); int temp=Get_Rank(tree[x]); Delete(temp); Insert(tree[x],1);}void Bottom(){ int x;scanf("%d",&x); int temp=Get_Rank(tree[x]); Delete(temp); Insert(tree[x],n);}void Insert(){ int x,y;scanf("%d%d",&x,&y); int temp=Get_Rank(tree[x]); Delete(temp); Insert(tree[x],temp+y);}void Ask(){ int x;scanf("%d",&x); printf("%d\n",Get_Rank(tree[x])-1);}void Query(){ int x;scanf("%d",&x); Find(root,x+1,null); printf("%d\n",root->num);}void Output(abcd *x){ if(x==null) return ; Output(x->ls); cout< num<<' '; Output(x->rs); if(x==root) puts("");}int main(){ int i; char p[20]; cin>>n>>m; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) tree[i]=new abcd(i); Initialize(); for(i=1;i<=m;i++) { scanf("%s",p); switch(p[0]) { case 'T':Top();break; case 'B':Bottom();break; case 'I':Insert();break; case 'A':Ask();break; case 'Q':Query();break; } //Output(root); }}