文艺平衡树（区间翻转）

· · 算法·理论

引入

一般像线段树这样的数据结构可以维护一些静态序列上的信息，但是如果这个序列要插入，删除或者翻转某些节点，这样就很难用那些数据结构实现了。
其实之前我很难想象平衡树能去处理序列问题，不过写完无旋Treap后，大概能理解很多

无旋Treap实现区间翻转

我们考虑一个区间翻转操作，可以被转化成这个在区间上的节点的所有子树交换左右子树，这个可以手模一下理解。
然而直接这样做甚至不如暴力，于是引入类似线段树的懒标记，就能实现单次区间翻转操作 \mathcal{O}(\log n) 的复杂度了。
合并和分裂要下传懒标记，分裂是按位置分裂，有一些细节要注意。
感觉这玩意拓展性很高，晚点在这里贴一些启发性的例题。

代码

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

#define ull unsigned long long
#define fi first
#define se second
#define mp make_pair

const int MAXN=100010;

struct node{
    int l,r; //左右儿子
    int val,siz,cnt; //真值，子树大小，这个数个数
    ull pri; //大根堆优先度
    bool laz; //翻转
};
struct treap{
    mt19937_64 rand; //随机数生成器
    int cnt,root;//节点数，根
    node t[MAXN];
    treap();
    int newnode(int val);//生成新节点
    void upd(int p);//更新子树大小
    void pd(int p); //下传标记
    void rev(int p); //翻转
    pair<int,int> split(int p,int key);//分裂
    int merge(int u,int v);//合并节点
    void insert(int val);//插入节点
    void reverse(int l,int r);//区间翻转
    void print(int p);//输出
}tree;

template<typename T>
void read(T& x);
template<typename T>
void write(T x);
template<typename T>
void write(T x,char c);

int n,m,l,r;

int main(){
    read(n); read(m); 
    for (int i=1;i<=n;i++) tree.insert(i);
    for (int i=1;i<=m;i++){
        read(l); read(r); tree.reverse(l,r);
    }
    tree.print(tree.root);
    return 0;
}

template<typename T>
void read(T& x){
    x=0; bool f=0; char ch=getchar();
    while (ch>'9'||ch<'0') {
        if (ch=='-') f=1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    x=f?-x:x;
}

template<typename T>
void write(T x){
    if (x<0) putchar('-'),x=-x;
    if (x>9) write(x/10);
    putchar(x%10+'0');
}

template<typename T>
void write(T x,char c){
    write(x); 
    putchar(c);
}

treap::treap(){
    rand.seed(time(nullptr));
}

int treap::newnode(int val){ //生成新节点
    ++cnt; 
    t[cnt].val=val; 
    t[cnt].cnt=t[cnt].siz=1;
    t[cnt].pri=rand();
    return cnt;
}

void treap::upd(int p){ //更新子树大小
    t[p].siz=t[t[p].l].siz+t[t[p].r].siz+t[p].cnt;
}

pair<int,int> treap::split(int p,int key){ //按照位置分裂
    if (!p) return mp(0,0);
    pd(p);
    if (t[t[p].l].siz>=key){ //在左边，继续裂，注意要用左子树大小
        auto temp=split(t[p].l,key); 
        t[p].l=temp.se;
        upd(p);
        return mp(temp.fi,p);
    }
    else{ //在右边，继续裂，记得差分
        auto temp=split(t[p].r,key-t[t[p].l].siz-t[p].cnt); 
        t[p].r=temp.fi;
        upd(p);
        return mp(p,temp.se); 
    }
}

int treap::merge(int u,int v){ //合并节点
    if (!u) return v;
    if (!v) return u;
    pd(u); pd(v);
    if (t[u].pri>t[v].pri){ //满足大根堆性质，u为根
        t[u].r=merge(t[u].r,v);
        upd(u);
        return u;
    }
    else {
        t[v].l=merge(u,t[v].l);//v为根
        upd(v);
        return v;
    }
}

void treap::insert(int val){//插入节点
    auto temp1=split(root,val);
    auto temp2=split(temp1.fi,val-1); //先分裂
    if (!temp2.se) temp2.se=newnode(val);
    else t[temp2.se].cnt++,upd(temp2.se);
    root=merge(merge(temp2.fi,temp2.se),temp1.se);  //再合并
}
void treap::rev(int p){ //翻转节点
    if (!p) return;
    swap(t[p].l,t[p].r);
    t[p].laz^=1; 
}
void treap::pd(int p){ //下传标记
    if (!t[p].laz) return;
    rev(t[p].l); rev(t[p].r);
    t[p].laz=0;
}
void treap::reverse(int l,int r){ //区间翻转
    auto temp1=split(root,l-1);
    auto temp2=split(temp1.se,r-l+1); //找到要反转的区间
    rev(temp2.fi); 
    root=merge(temp1.fi,merge(temp2.fi,temp2.se));
}
void treap::print(int p){ //输出
    if (!p) return;
    pd(p);
    print(t[p].l);
    write(t[p].val,' ');
    print(t[p].r);
}