hdu4453

题解：

splay模板

删除，翻转等等

代码：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int M=;

int root,N,ch[M][],pre[M],a[M],size[M],key[M],add[M],rev[M],s[M],tot2,tot1;

#define Key_value ch[ch[root][1]][0]

void NewNode(int &r,int f,int val)

{

    if (tot2)r=s[tot2--];

    else r+=++tot1;

    ch[r][]=ch[r][]=;

    pre[r]=f;

    size[r]=;

    key[r]=val;

    rev[r]=;

    add[r]=;

}

void pushup(int r){size[r]=size[ch[r][]]+size[ch[r][]]+;}

void build(int &x,int l,int r,int f)

{

    if (l>r)return;

    int mid=(l+r)>>;

    NewNode(x,f,a[mid]);

    build(ch[x][],l,mid-,x);

    build(ch[x][],mid+,r,x);

    pushup(x);

}

void update_add(int r,int x)

{

    if (!r)return;

    add[r]+=x;

    key[r]+=x;

}

void update_rev(int r)

{

    if (!r)return;

    swap(ch[r][],ch[r][]);

    rev[r]^=;

}

void pushdown(int r)

{

    if (add[r])

     {

        update_add(ch[r][],add[r]);

        update_add(ch[r][],add[r]);

        add[r]=;

     }

    if (rev[r])

     {

        update_rev(ch[r][]);

        update_rev(ch[r][]);

        rev[r]=;

     }

}

void Rotate(int x,int kind)

{

    int y=pre[x];

    pushdown(y);

    pushdown(x);

    ch[y][!kind]=ch[x][kind];

    pre[ch[x][kind]]=y;

    if (pre[y])ch[pre[y]][ch[pre[y]][]==y]=x;

    pre[x]=pre[y];

    ch[x][kind]=y;

    pre[y]=x;

    pushup(y);

}

void Splay(int r,int goal)

{

    pushdown(r);

    while(pre[r]!=goal)

     {

        if (pre[pre[r]]==goal)

         {

            pushdown(pre[r]);

            pushdown(r);

            Rotate(r,ch[pre[r]][]==r);

         }

        else

         {

            pushdown(pre[pre[r]]);

            pushdown(pre[r]);

            pushdown(r);

            int y=pre[r],kind=(ch[pre[y]][]==y);

            if (ch[y][kind]==r)

             {

                Rotate(r,!kind);

                Rotate(r,kind);

             }

            else

             {

                Rotate(y,kind);

                Rotate(r,kind);

             }

         }

     }

    pushup(r);

    if (goal==)root=r;

}

int get_kth(int r,int k)

{

    pushdown(r);

    int t=size[ch[r][]]+;

    if (t==k)return r;

    if (t>k)return get_kth(ch[r][],k);

    else return get_kth(ch[r][],k-t);

}

void change(int &poss,int k)

{

    int pos=get_kth(root,poss);

    Splay(pos,);

    int tmp=size[ch[root][]]+;

    Splay(get_kth(root,),);

    Splay(get_kth(root,tmp),root);

    tmp=Key_value;

    Key_value=;

    pushup(ch[root][]);

    pushup(root);

    Splay(get_kth(root,size[root]-),);

    Key_value=tmp;

    pre[Key_value]=ch[root][];

    pushup(ch[root][]);

    pushup(root);

    Splay(get_kth(root,),);

    Splay(get_kth(root,k+),root);

}

void Add(int &poss,int k2,int x)

{

    change(poss,k2);

    update_add(Key_value,x);

    pushup(ch[root][]);

    pushup(root);

    poss=;

}

void Reverse(int &poss,int k1)

{

    change(poss,k1);

    update_rev(Key_value);

    pushup(ch[root][]);

    pushup(root);

    poss=;

}

void Insert(int &poss,int x)

{

    int pos=get_kth(root,poss);

    Splay(pos,);

    Splay(get_kth(root,size[ch[root][]]+),root);

    NewNode(Key_value,ch[root][],x);

    pushup(ch[root][]);

    pushup(root);

}

void erase(int r)

{

    if (r)

     {

        s[++tot2]=r;

        erase(ch[r][]);

        erase(ch[r][]);

     }

}

void Delete(int &poss)

{

    int pos=get_kth(root,poss);

    Splay(pos,);

    int tmp=size[ch[root][]]+;

    Splay(get_kth(root,tmp-),);

    Splay(get_kth(root,tmp+),root);

    erase(Key_value);

    pre[Key_value]=;

    Key_value=;

    pushup(ch[root][]);

    pushup(root);

    if (tmp==size[root])poss=;

    else poss=tmp;

}

void Move(int &poss,int x)

{

    int pos=get_kth(root,poss);

    if (x==)

     {

        Splay(pos,);

        int tmp=size[ch[root][]];

        if (size[ch[root][]]==)tmp=size[root]-;

        poss=tmp;

     }

    else

     {

        Splay(pos,);

        int tmp=size[ch[root][]]+;

        if (tmp==size[root])tmp=;

        poss=tmp;

     }

}

int Query(int &poss)

{

    int pos=get_kth(root,poss);

    Splay(pos,);

    return key[root];

}

int main()

{

    int n,m,k1,k2,t=;

    while(scanf("%d%d%d%d",&n,&m,&k1,&k2)!=EOF)

     {

        N=n;

        if (n==&&m==&&k1==&&k2==)break;

        printf("Case #%d:\n",t++);

        for (int i=;i<=n;i++)scanf("%d",&a[i]);

        int poss=,sum=n;

        root=tot1=tot2=;

        ch[root][]=ch[root][]=size[root]=key[root]=add[root]=pre[root]=;

        rev[root]=;

            NewNode(root,,-);

            NewNode(ch[root][],root,-);

        build(Key_value,,N,ch[root][]);

        pushup(ch[root][]);

        pushup(root);

        for (int i=;i<=m;i++)

         {

            char a[];

            scanf("%s",a);

            if (a[]=='q')

             {

                int res=Query(poss);

                printf("%d\n",res);

             }

            else if (a[]=='r')Reverse(poss,k1);

            else if (a[]=='i')

             {

                int x;

                sum+=;

                scanf("%d",&x);

                Insert(poss,x);

             }

            else if (a[]=='d')

             {

                sum-=;

                Delete(poss);

             }

            else if (a[]=='m')

             {

                int x;

                scanf("%d",&x);

                if (x==)

                 {

                    if (poss==)poss=sum+;

                    else poss-=;

                 }

                if (x==)

                 {

                    if (poss==sum+)poss=;

                    else poss+=;

                 }

             }

            else if (a[]=='a')

             {

                int x;

                scanf("%d",&x);

                Add(poss,k2,x);

             }

         }

     }

    return ;

}