左偏树模板（以洛谷P3377 为例）

Bertha 。 2022-04-14 02:19 306阅读 0赞

## 题目：[点击打开链接][Link 1]   题意：略。   分析：左偏树（可并堆）模板题，配对堆或者斐波那契堆也可以做。左偏树入门参考[https://www.luogu.org/problemnew/solution/P3377?&page=2][https_www.luogu.org_problemnew_solution_P3377_page_2]。   代码： ##

#include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    const ll mod = 1e9+7;
    const int N = 1e6+10;
    
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int n,m;
    int val[N],f[N],dis[N],ch[N][2];
    
    int mg(int x,int y) {///返回值为编号，是直接父亲的编号 
        if(x==0||y==0) return x+y;
        if( (val[x]>val[y]) || (val[x]==val[y] && x>y ) ) swap(x,y);
        ch[x][1] = mg(ch[x][1],y);
        f[ch[x][1]]=x;
        if(dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][0],ch[x][1]);///维持左偏性质 
        dis[x]=dis[ch[x][1]]+1;
        return x;
        ///因为是左偏树,所以右边的深度要小,左边深度要大
        ///所以维护距离时,以右儿子为标准统计深度 
    }
    
    int getf(int x) {///不用路径压缩,不赋初值，所以他祖先没有父亲(为0 
        while(f[x]) x=f[x];///一直找,直到这个节点没父亲即为祖先 
        return x;
    }
    
    void pop(int x) {
        val[x]=-1;
        f[ch[x][0]]=f[ch[x][1]]=0;///去掉父亲
        mg(ch[x][0],ch[x][1]);///合并儿子
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&val[i]);
        while(m--) {
            int op,x,y;
            scanf("%d",&op);
            if(op==1) {
                scanf("%d%d",&x,&y);
                if( val[x]==-1 || val[y]== -1 || x==y || getf(x)==getf(y) ) continue;
                mg(getf(x),getf(y));
            }
            else {
                scanf("%d",&x);
                if(val[x]==-1) printf("-1\n");
                else printf("%d\n",val[getf(x)]),pop(getf(x));
            }
        }
        return 0;
    }

[Link 1]: https://www.luogu.org/problemnew/show/P3377
[https_www.luogu.org_problemnew_solution_P3377_page_2]: https://www.luogu.org/problemnew/solution/P3377?&page=2