Description

1． Top S——表示把编号为S的书放在最上面。

2． Bottom S——表示把编号为S的书放在最下面。

3． Insert S T——T∈{-1，0，1}，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书；

4． Ask S——询问编号为S的书的上面目前有多少本书。

5． Query S——询问从上面数起的第S本书的编号。

Solution

打算用它练习一下\(fhqTreap\)。

比较烦的是还要记下每个点的\(fa\)指针，才能计算它的排名

各种修改都是\(split\)然后\(merge\)一下就行了，简单

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 80005class fhqTree{    private:        int pri[MN],siz[MN],id[MN],fa[MN],ls[MN],rs[MN],val[MN],rt,sz;        inline unsigned int random()        {            static unsigned int x=23333;            return x^=x<<13,x^=x>>17,x^=x<<5;        }        inline int up(int x){if(ls[x])fa[ls[x]]=x;if(rs[x])fa[rs[x]]=x;return siz[x]=siz[ls[x]]+siz[rs[x]]+1;}        inline void Split(int x,int k,int&rt1,int&rt2)        {            if(!x) return(void)(rt1=rt2=0);            if(siz[ls[x]]>=k) Split(ls[x],k,rt1,ls[x]),up(x),rt2=x;            else Split(rs[x],k-siz[ls[x]]-1,rs[x],rt2),up(x),rt1=x;        }        inline int Merge(int rt1,int rt2)        {            if(!(rt1*rt2)) return rt1|rt2;            if(pri[rt1]
     
      r) return;x=++sz;pri[x]=random();            if(l==r) return (void)(siz[x]=1,val[x]=read(),id[val[x]]=x);int mid=(l+r)>>1;            Build(ls[x],l,mid-1);val[x]=read();id[val[x]]=x;Build(rs[x],mid+1,r);up(x);        }        inline int find(int x)        {            #define get(x) (rs[fa[x]]==x)            int res=siz[ls[x]]+1;            for(;(x^rt)&&x;x=fa[x]) if(get(x)) res+=siz[ls[fa[x]]]+1;            return res;        }        inline void Output(int x)        {            if(!x) return;            Output(ls[x]);printf("%d %d\n",val[x],val[fa[x]]);Output(rs[x]);        }    public:        inline void build(int n){Build(rt,1,n);}        inline void output(){Output(rt);puts("");}        inline void Top(int x)        {            register int k=find(id[x]),rt1,rt2,rt3,rt4;            Split(rt,k,rt1,rt2);Split(rt1,k-1,rt3,rt4);            rt=Merge(rt4,Merge(rt3,rt2));        }        inline void Bottom(int x)        {            register int k=find(id[x]),rt1,rt2,rt3,rt4;            Split(rt,k,rt1,rt2);Split(rt1,k-1,rt3,rt4);            rt=Merge(rt3,Merge(rt2,rt4));        }        inline void Move(int x,int T)        {            if(!T) return;            register int k=find(id[x]),rt1,rt2,rt3,rt4,rt5,rt6;            Split(rt,k,rt1,rt2);Split(rt1,k-1,rt3,rt4);            if(T>0) Split(rt2,1,rt5,rt6),rt=Merge(rt3,Merge(rt5,Merge(rt4,rt6)));            else  Split(rt3,k-2,rt5,rt6),rt=Merge(rt5,Merge(rt4,Merge(rt6,rt2)));        }        inline void Ask(int x){printf("%d\n",find(id[x])-1);}        inline void Query(int k)        {            register int rt1,rt2,rt3,rt4;            Split(rt,k,rt1,rt2);Split(rt1,k-1,rt3,rt4);            printf("%d\n",val[rt4]);rt=Merge(rt3,Merge(rt4,rt2));        }}T;int main(){    register int x,n=read(),m=read(),i;T.build(n);    register char s[20];    while(m--)    {        scanf("%s",s);x=read();        if(s[0]=='T') T.Top(x);        if(s[0]=='B') T.Bottom(x);        if(s[0]=='I') T.Move(x,read());        if(s[0]=='A') T.Ask(x);        if(s[0]=='Q') T.Query(x);    }    return 0;}
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！