左偏树与可持久化左偏树

上次thucamp有一道题：有n+1个multiset，编号从0开始，一开始都为空。第i次操作(i=1,2,…,n)有三种可能（输入确定），令$s_i=s_j\bigcup x$, 或者$s_i=s_x\bigcup s_y$,或者$s_i=s_j$然后删除最小元素，每次操作都要查询一次最小值。

因为当时不会左偏树，所以我尝试用线段树来写，但是发现线段树并不适合这一道题。比如说，比如某两个multiset都有1~10000的每个数，那么线段树上就会形成一个有接近10000个节点的满二叉树，然后每次合并都要把全部的点遍历一次，这样必然会超时。毕竟，题目只需要查询最小值，而线段树能够满足更多的功能。

后面听说要用左偏树来做，于是我就打算上网学习一下。

我先做了洛谷的一个模板，然后就意识到这个东西完全可以用于可持久化。

P3377 【模板】左偏树/可并堆

其实这道题有很多的方法可以做。

但是学习完左偏树以后，感觉这种算法非常符合直觉，感觉顺利成章的想就能想出来，而且代码很短，十分优美。

左偏树也叫可并堆，顾名思义，它就是一种堆，但是合并非常的快。那么我们现在先思考一下怎么合并两个堆。一种常见的想法就是用启发式合并，这样的时间复杂度是双log的，而且不能可持久化。

现在考虑直接合并两个堆，可以利用堆的高度是log的性质合并。而不是一个个节点的插进去。假设我们要求的是小根堆，那么我们肯定要先固定小的那个点，然后把根值更大的一堆和它其中的一个儿子合并，那么我们应该如何选择儿子呢？特别地，如果存在空儿子，那么我们就直接把大的根作为空儿子就行。也就是说，只要我们合并能遇到空儿子，就能结束合并，因此我们要找到最近的空儿子。很显然而且很重要的，假设这个最近的距离为d，那么堆至少有$2^d-1$个点，这就说明$d$的大小就是log的。

综上，我们可以维护距离每个点最近的空儿子，合并的时候就可以往那边走。左偏树的做法就是依靠对换左右儿子，始终把这个最近的空儿子放在右边，因此在左偏树中，每次合并都只需要在确定哪个为当前根节点以后往右走即可，时间复杂度是单log的。

现在说一下几种操作的具体实现：
1.合并两个堆，这就是我们前面说的。
2.删除根节点，就是合并左右儿子。
3.查找每个节点所在的根节点。因为深度不确定，所以不能在左偏树上面直接找，而是要专门打一个并查集维护。
4.删除某个节点。（我自己的想法）合并其左右儿子，把节点从堆中删除，把堆的根节点和已经合并的左右儿子再次合并（虽然常数大但是很好记，而且不用专门打一个函数）。
5.想查询历史版本。我们的目的是不改变原有节点的关系，因此对于任意要修改的节点，新建一个节点来代替它。

洛谷P3377

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){
    x=0;int f=0;char s=getchar();
    while(!isdigit(s))f|=s=='-',s=getchar();
    while(isdigit(s))x=x*10+s-48,s=getchar();
    x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){
    if(x<0)putchar('-'),x=-x;
    do{buf[++cc]=int(x%10);x/=10;}while(x);
    while(cc)putchar(buf[cc--]+'0');
}
const int N=1e5+10;
int n,m;
struct heap{
    int lc,rc,d,val;
}t[N];
int fa[N],rt[N];
bool v[N];
int findfa(int x){return x==fa[x]?x:fa[x]=findfa(fa[x]);}
int merge(int x,int y){
    if(!x||!y)return x|y;
    if(t[x].val>t[y].val)swap(x,y);
    t[x].rc=merge(t[x].rc,y);
    if(t[t[x].lc].d<t[t[x].rc].d)
        swap(t[x].lc,t[x].rc);
    t[x].d=t[t[x].rc].d+1;
    return x;
}
void solve(){
    qr(n),qr(m);
    rep(i,1,n){
        int x;qr(x);
        t[i].lc=t[i].rc=t[i].d=0;
        t[i].val=x;
        fa[i]=i;rt[i]=i;
    }
    while(m--){
        int op;qr(op);
        if(op==1){
            int x,y;qr(x),qr(y);
            if(v[x]||v[y]||findfa(x)==findfa(y))continue;
            x=rt[findfa(x)],y=rt[findfa(y)];
            rt[findfa(x)]=merge(x,y);
            fa[findfa(y)]=findfa(x);
        }
        else{
            int x;qr(x);
            if(v[x]){
                puts("-1");
                continue;
            }
            x=rt[findfa(x)];
            rt[findfa(x)]=merge(t[x].lc,t[x].rc);
            v[x]=1;
            qw(t[x].val);puts("");
        }
    }
}
int main(){
    int tt;tt=1;
    while(tt--)solve();
    return 0;
}

thucampd2G

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){
    x=0;int f=0;char s=getchar();
    while(!isdigit(s))f|=s=='-',s=getchar();
    while(isdigit(s))x=x*10+s-48,s=getchar();
    x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){
    if(x<0)putchar('-'),x=-x;
    do{buf[++cc]=int(x%10);x/=10;}while(x);
    while(cc)putchar(buf[cc--]+'0');
}
const int N=2e5+10;
struct heap{
    int lc,rc,d,val;
}t[N*70];int cnt,rt[N];
int n;
int merge(int x,int y){
    if(!x||!y)return x|y;
    if(t[x].val>t[y].val)swap(x,y);
    int p=++cnt;
    t[p]=t[x];
    t[p].rc=merge(t[p].rc,y);
    if(t[t[p].lc].d<t[t[p].rc].d)
        swap(t[p].lc,t[p].rc);
    t[p].d=t[t[p].rc].d+1;
    return p;
}
void print(int x){
    if(!x)return;
    cout<<t[x].val<<" ";
    print(t[x].lc);
    print(t[x].rc);
}
void solve(){
    qr(n);
    int s=0,ans=0;
    rep(i,1,n){
        int op;qr(op);
        if(op==1){
            int a,b;qr(a),qr(b);
            int pre,num;//qr(pre),qr(num);
            pre=(a+s)%i;
            num=(b+17*s)%(1000000001);
            t[++cnt].val=num;
            rt[i]=merge(rt[pre],cnt);
            ans=t[rt[i]].val;
            qw(ans);puts("");
        }
        else if(op==2){
            int a,b;qr(a),qr(b);
            int x,y;//qr(x),qr(y);
            x=(a+s)%i;
            y=(b+13*s)%i;
            rt[i]=merge(rt[x],rt[y]);
            if(!rt[i]){
                puts("empty");
                ans=0;
            }
            else{
                ans=t[rt[i]].val;
                qw(ans);puts("");
            }
        }
        else{
            int a;qr(a);
            int pre=(a+s)%i;
            // int pre;qr(pre);
            if(!rt[pre]){
                puts("empty");
                ans=0;
            }
            else{
                rt[i]=merge(t[rt[pre]].lc,t[rt[pre]].rc);
                ans=t[rt[pre]].val;
                qw(ans);puts("");
            }
        }
        s=(s+ans)%239017;
    }
}
int main(){
    // freopen("in.in","r",stdin);
    int tt;tt=1;
    while(tt--)solve();
    return 0;
}

原文地址：https://blog.csdn.net/zsyzClb/article/details/142393293

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！