SP7734 题解

· · 题解

这道题和文艺平衡树是双倍经验。

为了不会的同学们，我还是讲一讲。

详见我的博客园

fhq Treap

普通的 Treap 每次都要旋来旋去的，泰麻饭啦！于是出现了 fhq treap，也就是无旋 treap。

fhq treap 整体是拥有二叉搜索树的性质，但是它的每一个节点都会有一个附加权值，它的附加权值是符合堆的性质。附加权值需要随机，这样能让他尽量平衡，防止成一条链（当然也有可能成链，不过比出门被核弹创死的可能性还要低）。

treap 主要有两个操作 split 和 merge，也就是分裂与合并。

split

思想就是把一个 treap 分成两个。

用两种方法：按值分裂、按大小分裂。

首先是按值分裂，

这个就是按照他的权值，因为满足二叉搜索树，所以只需要判断比当前节点大还是小，就可以知道要分得值是在在左边还是右边。

void split(int p,int x,int &l,int &r){//分裂 
        if(!p){
            l=r=0;
            return ;
        }
        if(tree[p].key<=x){//判断权值是小还是大，根据权值去找比他小的。
            l=p;
            split(tree[l].r,x,tree[l].r,r);
        }else{
            r=p;
            split(tree[r].l,x,l,tree[r].l);
        }
        pushup(p);//标记上传
    }

然后就是按大小分裂：

void split(int p,int x,int &l,int &r) {
    if(p==0){
        l=r=0;
        return;
    }
    if(tree[tree[p].l].size+1<=x){
        l=p;
        split(tree[p].r,x-tree[tree[p].l].x-1,tree[p].r,r);
    } 
    else{
        r=p;
        split(tree[p].l,x,l,tree[p].l);
    }
    pushup(p);
}

merge

将两棵平衡树合起来，同时满足其 heap 值的堆性质，返回合并后的根序号，保证以 a 为根的树种每个节点的权值都小于以 b 为根的每个节点的权值。

当两棵子树其中有一棵为空时，将根设为 a+b（即非空树的根序号）；

当 val_a \leq val_b 时，将当前根设为 a，同时合并 l_r 和 b。

否则，将当前根设为 b，同时合并 a 和 r_l。


int merge(int l,int r){//合并 
    if(!l||!r)
        return l+r;
    if(tree[l].val<=tree[r].val){
        tree[l].r=merge(tree[l].r,r);
        pushup(l);
        return l;
    }else{
        tree[r].l=merge(l,tree[r].l);
        pushup(r);
        return r;
    }
}

好，fhq treap 的基本操作差不多讲完了，现在来谈谈这道题。

翻转

然后捏，由于上文说过，分裂的时候可以按照大小来划分，那么只需要将比 l 小的分裂出来，再把比 r 大的分裂出来，那么剩下的不就是 l 到 r 了吗。 

fhq_Treep.splitq(rt,y,dl,dr);
fhq_Treep.splitq(dl,x-1,dl,p);
tree[p].lazy^=1;
rt=fhq_Treep.mergeq(fhq_Treep.mergeq(dl,p),dr);

Code

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
inline int read()
{
    int f = 1, res = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        res = (res << 3ll) + (res << 1ll) + c - '0';
        c = getchar();
    }
    return f * res;
}
int n,m,cnt,dl,dr,tmp,rt,p;
int y,x;
struct node{
    int l,r,val,key,size,lazy;
}tree[N];
struct FHQ_Treep{
    int getrand(int x){
        tree[++cnt].val=x;
        tree[cnt].key=rand();//防止成链 
        tree[cnt].size=1;
        tree[cnt].l=0;
        tree[cnt].r=0;
        return cnt;
    }
    void pushup(int p){
        tree[p].size=tree[tree[p].l].size+tree[tree[p].r].size+1;
    }
    void pushdown(int u){//下传懒标记
        swap(tree[u].l,tree[u].r);
        tree[tree[u].l].lazy^=1;
        tree[tree[u].r].lazy^=1;
        tree[u].lazy=0;
    }
    void splitq(int p,int x,int &l,int &r){
        if(!p){
            l=r=0;
            return ;
        }
        if(tree[p].lazy)
            pushdown(p);
        if(tree[tree[p].l].size+1<=x){
            l=p;
            splitq(tree[p].r,x-tree[tree[p].l].size-1,tree[p].r,r);
        }
        else{
            r=p;
            splitq(tree[p].l,x,l,tree[p].l);
        }
        pushup(p);
    }
    int mergeq(int l,int r){//合并 
        if(!l||!r)
            return l+r;
        if(tree[l].key<tree[r].key){
            if(tree[l].lazy)
                pushdown(l);
            tree[l].r=mergeq(tree[l].r,r);
            pushup(l);
            return l;
        }
        else{
            if(tree[r].lazy)
                pushdown(r);
            tree[r].l=mergeq(l,tree[r].l);
            pushup(r);
            return r;
        }   
    }
    void print(int x){
        if(tree[x].lazy){
            pushdown(x);
        }
        if(tree[x].l)
            print(tree[x].l);
        printf("%d ",tree[x].val);
        if(tree[x].r)
            print(tree[x].r);
    }
}fhq_Treep;
int main(){
    n=read();m=read();
    for(int i=1;i<=n;++i)
        rt=fhq_Treep.mergeq(rt,fhq_Treep.getrand(i));
    for(int i=1;i<=m;++i){
        x=read();y=read();
        fhq_Treep.splitq(rt,y,dl,dr);
        fhq_Treep.splitq(dl,x-1,dl,p);
        tree[p].lazy^=1;
        rt=fhq_Treep.mergeq(fhq_Treep.mergeq(dl,p),dr);
    }
    fhq_Treep.print(rt);
    return 0;
}