时间戳

首页 > 技术文章 > 用splay来维护序列

用splay来维护序列

lijianlin1995 2014-02-14 14:18 原文

大白书例题 uva11922

留个splay模板

虚拟节点可以是放个最小的也可以放最大的，两种方法对同一个点会导致名次相差一。

弄一个节点当null确实比较方便

一开始序列转化成树居然可以直接搞出一条链也没问题，这个略屌。

#include <iostream>
#include <cstdio>

using namespace std;

struct Node
    {
        Node *ch[2];
        int v,s;

        bool flip;
        Node(){};
        Node(int v,Node* o):v(v)
            {s=v+1;ch[0]=ch[1]=o;}
        int cmp(int x) const{
            int l_size=ch[0]->s+1;
            if(x==l_size)return(-1);
            return (x<l_size)?(0):(1);
        }
        void maintain()
            {s=ch[0]->s+ch[1]->s+1;}
        void pushdown(){
            if(flip){
                flip=0;
                swap(ch[0],ch[1]);
                ch[0]->flip^=1;
                ch[1]->flip^=1;
            }
        }
    };
struct SplayTree
{
    Node *root,*null;
    SplayTree(){
        null=new Node;
        null->ch[0]=null->ch[1]=null;
        null->v=null->s=null->flip=0;
        root=null;
    }
    ~SplayTree(){
        clear(root);
        delete null;
    }
    void build(Node* &o,int n){
        //n=0既为最左边的虚拟节点
        if(n>=0){
            o=new Node(n,null);
            build(o->ch[0],n-1);
        }
    }
    void rotate(Node* &o,int d){
        Node* k=o->ch[d^1];
        o->ch[d^1]=k->ch[d];
        k->ch[d]=o;
        o->maintain();
        k->maintain();
        o=k;
    }

    void splay(Node* &o,int k){
        o->pushdown();
        int d=o->cmp(k);
        if(d==1) k-=o->ch[0]->s+1;
        if(d!=-1){
            Node* p=o->ch[d];
            p->pushdown();
            int d2=p->cmp(k);
            int k2=(d2==0 ? k : k-p->ch[0]->s-1);
            if(d2!=-1){
                splay(p->ch[d2],k2);
                if(d==d2)
                    rotate(o,d^1);
                else
                    rotate(o->ch[d],d);
            }
            rotate(o,d^1);
        }
        //cout<<(o->v)<<"("<<(o->ch[0]->v)<<","<<(o->ch[1]->v)<<")"<<endl;
    }
    Node* merge(Node* left,Node* right){
    //left should not be NULL
        splay(left,left->s);
        left->ch[1]=right;
        left->maintain();
        return left;
    }
    void split(Node* o,int k,Node* &left,Node* &right){
        splay(o,k);
        left=o;
        right=o->ch[1];
        o->ch[1]=null;
        left->maintain();
    }
    void clear(Node* &o)
    {
        if(o->ch[0]!=null)  clear(o->ch[0]);
        if(o->ch[1]!=null)  clear(o->ch[1]);
        delete o;
        o=null;
    }
    void print(Node* o)
    {
        if(o==null)return;
        o->pushdown();
        print(o->ch[0]);
        if(o->v>0)
            printf("%d\n",o->v);
        print(o->ch[1]);
    }
    void process(int a,int b){
        //a的名次是a+1 a-1的名次是a
        //左边序列到名次a
        Node *lef,*rig,*mid,*t;
        split(root,a,lef,t);
        split(t,b-a+1,mid,rig);
        mid->flip^=1;
        root=merge(merge(lef,rig),mid);
    }
};

int main()
{
    int n,m,a,b;
    scanf("%d%d",&n,&m);
    SplayTree s;
    s.build(s.root,n);
    for(int i=0;i<m;++i){
        scanf("%d%d",&a,&b);
        s.process(a,b);
    }
    s.print(s.root);
    return 0;
}

 

http://acm.hdu.edu.cn/showproblem.php?pid=3487

一开始一直WA是因为Node构造函数忘记给filp赋值。

#include <iostream>
#include <cstdio>

using namespace std;

/**
 * 对于长度不变的序列n是序列的长度，ansCount和n是用来控制输出空格的
 * 对于1..n的序列，左右添加了0和n+1作为虚拟节点防止分裂时出现空
 * 调用split和splay时要考虑虚拟节点对名次产生的影响
 * 其他函数参数中的名次都是原来序列的名次，虚拟节点产生对名次影响的考虑体现在函数实现中
 */
int n,ansCount;
struct Node
    {
        Node *ch[2];
        int v,s;
        bool flip;
        Node(){};
        Node(int v,Node* o):v(v)
            {
                flip=0;
                s=1;
                ch[0]=ch[1]=o;
            }
        int cmp(int x) const{
            int l_size=ch[0]->s+1;
            if(x==l_size)return(-1);
            return (x<l_size)?(0):(1);
        }
        void maintain()
            {s=ch[0]->s+ch[1]->s+1;}
        void pushdown(){
            if(flip){
                flip=0;
                swap(ch[0],ch[1]);
                ch[0]->flip^=1;
                ch[1]->flip^=1;
            }
        }
        void reverse()
        {
            flip^=1;
        }
    };
struct SplayTree
{
    Node *root,*null;
    SplayTree(){
        null=new Node;
        null->ch[0]=null->ch[1]=null;
        null->v=null->s=null->flip=0;
        root=null;
    }
    ~SplayTree(){
        clear(root);
        delete null;
    }
    Node* build(int l,int r){
        if(l>r) return null;
        int m=(l+r)>>1;
        Node* o = new Node(m,null);
        o->ch[0]=build(l,m-1);
        o->ch[1]=build(m+1,r);
        o->maintain();
        return o;
    }
    void rotate(Node* &o,int d){
        Node* k=o->ch[d^1];
        o->ch[d^1]=k->ch[d];
        k->ch[d]=o;
        o->maintain();
        k->maintain();
        o=k;
    }

    void splay(Node* &o,int k){
        o->pushdown();
        int d=o->cmp(k);
        if(d== 1) k-=o->ch[0]->s+1;
        if(d!=-1){
            Node* p=o->ch[d];
            p->pushdown();
            int d2=p->cmp(k);
            int k2=(d2==0 ? k : k-p->ch[0]->s-1);
            if(d2!=-1){
                splay(p->ch[d2],k2);
                if(d==d2)
                    rotate(o,d^1);
                else
                    rotate(o->ch[d],d);
            }
            rotate(o,d^1);
        }
        //cout<<(o->v)<<"("<<(o->ch[0]->v)<<","<<(o->ch[1]->v)<<")"<<endl;
    }

    //left should not be NULL
    Node* merge(Node* left,Node* right){
        splay(left,left->s);
        left->ch[1]=right;
        left->maintain();
        return left;
    }
    void split(Node* o,int k,Node* &left,Node* &right){
        splay(o,k);
        left=o;
        right=o->ch[1];
        o->ch[1]=null;
        left->maintain();
    }
    void clear(Node* &o)
    {
        if(o->ch[0]!=null)  clear(o->ch[0]);
        if(o->ch[1]!=null)  clear(o->ch[1]);
        delete o;
        o=null;
    }
    void print(Node* o)
    {
        if(o==null)return;
        o->pushdown();
        print(o->ch[0]);
        if(o->v>0 && o->v<=n)
            printf("%d%c",o->v," \n"[++ansCount==n]);
        print(o->ch[1]);

    }

    //把名次a到b切下来
    Node* cut(int a,int b){
        //a的名次是a+1 a-1的名次是a
        //左边序列到名次a
        Node *lef,*rig,*mid,*t;
        split(root,a,lef,t);//考虑到前半截序列多了一个虚拟节点0名字变大了1
        split(t,b-a+1,mid,rig);//后半截的前头没有虚拟节点
        root=merge(lef,rig);
        return mid;
    }

    //insert after A[rank]
    void insert(int rank,Node* mid){
        Node *lef,*rig;
        split(root,rank+1,lef,rig);//考虑到前半截序列多了一个虚拟节点0名字变大了1
        root=merge(merge(lef,mid),rig);
    }

    //翻转名字a到b的元素
    void flip(int a,int b){
        Node* mid = cut(a,b);
        mid->reverse();
        insert(a-1,mid);
        /*
        写法二
            两种写法都可以，时间也差不多
        splay(root,a);
        splay(root->ch[1],b-a+2);
        root->ch[1]->ch[0]->reverse();
        */
    }
};

int main()
{
    int m,a,b;char flag[10];
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==-1 && m==-1)break;
        SplayTree s;
        s.root=s.build(0,n+1);
        for(int i=0;i<m;++i){
            int a,b,c;
            scanf("%s",flag);
            switch(flag[0]){
                case 'C':{
                    scanf("%d%d%d",&a,&b,&c);
                    Node *mid=s.cut(a,b);
                    s.insert(c,mid);
                    break;
                }
                case 'F':{
                    scanf("%d%d",&a,&b);
                    s.flip(a,b);
                    break;
                }
            }
            //ansCount=0;s.print(s.root);
        }
        ansCount=0;
        s.print(s.root);
    }
    return 0;
}

 

 

 

推荐阅读