平衡树：treap学习笔记（3）

在（2）中我们写了无旋treap。然后我就找到了那道题qaq。

文艺平衡树

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

输入输出格式

输入格式：

第一行为n,m n表示初始序列有n个数，由1-n组成 m表示翻转操作次数。

输出格式：

输出一行n个数字，表示原始序列经过m次变换后的结果。

之前的treap里按权值维护，是一颗二叉查找树。而在这道题中好像和二叉查找树没什么关系。。

不过我们发现无旋treap只有在insert时维护了二叉查找树的性质。（这道题我们并用不到，我们要的是原数列）。然后我们知道笛卡尔树的中序遍历是原数列。所以我们能不能仿照笛卡尔树建树呢？

引用http://www.cnblogs.com/LadyLex/p/7182631.html的话。

二叉排序树的各种操作是不改变树的中序遍历的。所以这道题可以用各种二叉搜索树的操作。

我们可以用区间线段树的思想，加一个懒标记，然后操作时pushdown翻转。所谓翻转就是在要交换的区间树中交换左右儿子。（把要交换的区间拆出来）然后再合并回去。

最后中序遍历树 这样就巧妙地求出了区间翻转后的序列。

//补充：普通平衡树维护点权二叉搜索树，文艺平衡树维护数组下标二叉搜索树。

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define mp make_pair

const int MAXN=;
const int INF=;
typedef pair<int,int>par;

int n,m;
struct treap{
    int rt,cnt;
    int lson[MAXN],rson[MAXN],prio[MAXN],w[MAXN],size[MAXN],lzt[MAXN];
    inline void pushup(int o){size[o]=size[lson[o]]+size[rson[o]]+;}
    inline void pushdown(int p){
        if(lzt[p]){
            swap(lson[p],rson[p]);
            lzt[lson[p]]^=;lzt[rson[p]]^=;
            lzt[p]=;
        }
    }
    par split(int p,int x){
        if(!x)return mp(,p);
        pushdown(p);
        int l=lson[p],r=rson[p];
        if(x==size[l]){
            lson[p]=;pushup(p);return mp(l,p);
        }
        if(x==size[l]+){
            rson[p]=;pushup(p);return mp(p,r);
        }
        if(x<size[l]){
            par tem=split(l,x);
            lson[p]=tem.second;pushup(p);return mp(tem.first,p);
        }
        par tem=split(r,x-size[l]-);
        rson[p]=tem.first;pushup(p);return mp(p,tem.second);
    }
    int merge(int x,int y){
        if(!x||!y)return x+y;
        pushdown(x);pushdown(y);
        if(prio[x]<prio[y]){
            rson[x]=merge(rson[x],y);pushup(x);return x;
        }
        else {
            lson[y]=merge(x,lson[y]);pushup(y);return y;
        }
    }
    void build(int &p,int l,int r){//建树过程可以模拟一下。会存在0.
        if(l>r){
            p=;return;
        }
        int mid=(l+r)>>;
        w[++cnt]=mid-;prio[cnt]=rand();size[cnt]=;lzt[cnt]=;p=cnt;
        build(lson[p],l,mid-);
        build(rson[p],mid+,r);
        pushup(p);
    }
    void dfs(int p){
        if(!p)return;
        pushdown(p);
        dfs(lson[p]);
        if(w[p]>=&&w[p]<=n)printf("%d ",w[p]);
        dfs(rson[p]);
    }
}treap;

int main(){
//  freopen("5.in","r",stdin);
//  freopen("5.out","w",stdout);
    srand();
    scanf("%d%d",&n,&m);
    treap.build(treap.rt,,n+);//有0存在所以补2位。其实1位也可以AC了
    int llw,rrw;
    int x,y,c,d;
    while(m--){
        scanf("%d%d",&llw,&rrw);
        par t1=treap.split(treap.rt,rrw+);//因为建树的方式有0存在。
        par t2=treap.split(t1.first,llw);//同理
        treap.lzt[t2.second]^=;
        treap.rt=treap.merge(t2.first,t2.second);
        treap.rt=treap.merge(treap.rt,t1.second);
    }
    treap.dfs(treap.rt);
    return ;
}