首页 > 其他 > 详细

左偏树学习笔记

时间:2019-07-24 23:07:32      阅读:126      评论:0      收藏:0      [点我收藏+]

定义

我不知道

特殊作用

可并

从题目中得到的用处

并查集优化

左偏树主要有两个操作,一个是合并,一个是删除。

对于合并,直接更新,可以看下面的代码。

对于删除,也可以直接更新,注意把要删除的节点在并查集中保留,因为它可能是其他节点找爸爸路上的必经之点,可以看下面的代码。

做题

洛谷模板题目代码

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

const int N = 100000 + 5;
struct In {
    const In operator, (int & a) const {
        a = 0;
        int f = 1;
        char k = getchar ();
        while (k > '9' || k < '0') {
            if (k == '-') {
                f = -1;
            }
            k = getchar ();
        }
        while (k >= '0' && k <= '9') {
            a = a * 10 + k - '0';
            k = getchar ();
        }
        a *= f;
        return * this;
    }
}in;
struct Node {
    int val, id;
    bool operator < (Node x) {
        return val == x.val ? id < x.id : val < x.val;
    }
    bool operator > (Node x) {
        return val == x.val ? id > x.id : val > x.val;
    }
}info[N];
int n, m, fa[N], ch[N][2], dis[N];
bool vis[N];

inline int Find (int u) {
    return fa[u] == u ? u : fa[u] = Find (fa[u]);
}

inline int merge (int x, int y) {
    if (!x || !y) {
        return x + y;
    }
    if (info[x] > info[y]) {
        swap (x, y);
    }
    ch[x][1] = merge (ch[x][1], y);
    fa[ch[x][1]] = x;
    if (dis[ch[x][1]] > dis[ch[x][0]]) {
        swap (ch[x][1], ch[x][0]);
    }
    dis[x] = dis[ch[x][1]] + 1;
    return x;
}

inline void query (int u) {
    if (vis[u]) {
        printf ("-1\n");
        return ;
    }
    u = Find (u);
    printf ("%d\n", info[u].val);
    vis[u] = 1;
    ch[u][0] = merge (ch[u][0], ch[u][1]);
    fa[ch[u][0]] = ch[u][0];
    fa[u] = ch[u][0];
    ch[u][0] = ch[u][1] = 0;
}

inline void Merge (int u, int v) {
    if (vis[u] || vis[v]) {return ;}
    u = Find (u);
    v = Find (v);
    if (u == v) {return ;}
    merge (u, v);
}

int main () {
    in, n, m;
    for (int i = 1; i <= n; ++i) {
        in, info[i].val;
        info[i].id = i;
        fa[i] = i;
    }
    for (int i = 1; i <= m; ++i) {
        int opt, x, y;
        in, opt, x;
        if (opt == 1) {
            in, y;
            Merge (x, y);
        }
        else {
            query (x);
        }
    }
    return 0;
}

左偏树学习笔记

原文:https://www.cnblogs.com/ChiTongZ/p/11241187.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!