首页 > 代码库 > luogu 【P3377】 【模板】左偏树
luogu 【P3377】 【模板】左偏树
左偏树模板。。。
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <cctype> #include <iostream> #define For(i, l, r) for(int i = (l); i <= (int)(r); ++i) #define Fordown(i, r, l) for(int i = (r); i >= (int)(l); --i) #define Set(a, v) memset(a, v, sizeof(a)) using namespace std; inline int read(){ int x = 0, fh = 1; char ch; for(; !isdigit(ch); ch = getchar()) if (ch == ‘-‘) fh = -1; for(; isdigit(ch); ch = getchar()) x = (x<<1) + (x<<3) + (ch^‘0‘); return x * fh; } struct node { int lc, rc, val; //分别是left_child左儿子, right_child右儿子, value 键值 }; const int max_node = 100100; //最大子节点个数 node lt[max_node]; //leftist_tree 左偏树 int dist[max_node], fa[max_node]; //左偏树距离dist:到最右叶子节点边的条数 //并查集父亲数组fa void make_tree (int x) { lt[x].lc = lt[x].rc = dist[x] = 0; //清空它的左右儿子和距离(新建一个树) } int merge (int a, int b) { if (a == 0) return b; //a为空 返回b if (b == 0) return a; //b为空 返回a if (lt[a].val > lt[b].val) swap(a, b); //将根节点设为a(值较小的那个) lt[a].rc = merge(lt[a].rc, b); fa[lt[a].rc] = a; //将b合并到a的右子树上 并将右子树父亲设为a if (dist[lt[a].rc] > dist[lt[a].lc]) swap(lt[a].lc, lt[a].rc); //右子节点距离大于左子节点 不符合左偏树性质则交换左右子树 if (lt[a].rc == 0) dist[a] = 0; //右子树为空 距离为0 即直接到自己 else dist[a] = dist[lt[a].rc] + 1; //否则按照性质 距离为右子节点的距离+1 return a; //返回a节点 } int find (int x) { return fa[x] = fa[x] == x ? x : find(fa[x]); //并查集操作 } int main(){ int n = read(), m = read(); For (i, 1, n) { lt[i].val = read(); make_tree(i); fa[i] = i; } while (m--) { int opt = read(); if (opt == 1) { int a = read(), b = read(); int root_a = find(a), root_b = find(b); if (root_a == root_b) continue; //在同一个堆里就不合并 if (lt[a].val == 0 || lt[b].val == 0) continue; //这个数已被删掉也不合并 // cout << "merge: " << root_a << ‘ ‘ << root_b << endl; int tmp = merge(root_a, root_b); fa[root_a] = fa[root_b] = tmp; //将两个节点父亲设为合并后的父亲 } else { int a = read(); int root_a = find(a); if (lt[a].val == 0) {printf ("-1\n"); continue;} //已被删除 输出-1 // cout << "find: " << root_a << endl; printf ("%d\n", lt[root_a].val); int tmp = merge (lt[root_a].lc, lt[root_a].rc); fa[lt[root_a].lc] = fa[lt[root_a].rc] = tmp; //将左右子树的父亲设为它们合并后的父亲 lt[root_a].lc = lt[root_a].rc = lt[root_a].val = 0; //删除堆顶 } } }
luogu 【P3377】 【模板】左偏树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。