uva11922(splay模板)排列变换

2017-08-18 106点热度 0人点赞

排列变换(Permutation Transformer, UVa 11922
你的任务是根据
m条指令改变排列{1
23
n} 。 每条指令(a
b) 表示取出第ab个元素, 翻转后添加到排列的尾部。
【输入格式】
输入仅一组数据。 第一行为整数
nm1≤n
m≤100000) 。 以下m行 每行为一条指令a
b1≤a≤b≤n) 。
【输出格式】
输出
n行, 即最终排列。
【分析】

用一个可分裂合并的序列来表示整个序列, 则截取出序列并放到序列末尾的操作是不难实现的。 如何实现翻转呢?
根据前面线段树部分的经验, 可以用标记来完成。 给结点增加一个
flip标记(表示以本结点为根的子树有没有旋转过) , 也可以写出与前面类似的pushdown函数, 代码如下

#include 
#include 

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 (xs+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个结点 
        //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);
        }
    }
    Node* merge(Node* left,Node* right){
	/*
	把序列left和right连接在一起,left在左边,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){
    	//把序列o分裂成两个连续的子序列,左子序列包含左边k个元素, 右子序列包含其余的元素
        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("%dn",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

未经允许不得转载!uva11922(splay模板)排列变换

本文地址:https://ai.52learn.online/399

站长邮箱:ai52learn@foxmail.com