左偏树模板
左偏树 (Leftist Tree) 是一种特殊的堆有序 (heap-ordered) 二叉树。
普通的二叉堆合并的复杂度为 O(n)，即使采用启发式合并也需要 O(log2n) 的时间。
假定我们的合并方法是将“副堆”往“主堆”右子树中合适的位置插入。
我们发现，合并的最坏情况出现在二叉堆成为一条右链时。
考虑到交换左右子树不会破坏堆的性质，我们可以通过该操作减小堆的深度。
最玄学的方法是每次插入时都交换经过节点的左右子树，这样可以在一定程度上使左右子树大小相近，做到单次均摊 logn 的复杂度。这类数据结构叫作斜堆。
而左偏树是斜堆的一种较为珂学科学的实现方法。
我们发现，堆合并的效率取决于主堆右链的长度。因为只要递归到有一个子树为空则合并完成。
对于每个节点，增加一个成员变量 dist，表示该节点起右链的长度。
每次合并时，仅当左儿子的 dist 小于右儿子的 dist 时交换左右子树，保证右链不会过长。
这样就可以做到单次严格 logn 的复杂度。
模板题：洛谷 3377 【模板】左偏树（可并堆）。
注意删除节点时要将其子树的父指针置为子树本身。
Problem:
题目描述
如题，一开始有N个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：
操作1： 1 x y 将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在同一个堆内，则无视此操作）
操作2： 2 x 输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）
输入输出格式
输入格式：
第一行包含两个正整数N、M，分别表示一开始小根堆的个数和接下来操作的个数。
第二行包含N个正整数，其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。
接下来M行每行2个或3个正整数，表示一条操作，格式如下：
操作1 ： 1 x y
操作2 ： 2 x
输出格式：
输出包含若干行整数，分别依次对应每一个操作2所得的结果。
输入输出样例
5 5 1 5 4 2 3 1 1 5 1 2 5 2 2 1 4 2 2 2
1 2
说明
当堆里有多个最小值时，优先删除原序列的靠前的，否则会影响后续操作1导致WA。
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=10，M<=10
对于70%的数据：N<=1000，M<=1000
对于100%的数据：N<=100000，M<=100000
样例说明：
初始状态下，五个小根堆分别为:{1}、{5}、{4}、{2}、{3}。
第一次操作，将第1个数所在的小根堆与第5个数所在的小根堆合并，故变为四个小根堆：{1,3}、{5}、{4}、{2}。
第二次操作，将第2个数所在的小根堆与第5个数所在的小根堆合并，故变为三个小根堆：{1,3,5}、{4}、{2}。
第三次操作，将第2个数所在的小根堆的最小值输出并删除，故输出1，第一个数被删除，三个小根堆为：{3,5}、{4}、{2}。
第四次操作，将第4个数所在的小根堆与第2个数所在的小根堆合并，故变为两个小根堆：{2,3,5}、{4}。
第五次操作，将第2个数所在的小根堆的最小值输出并删除，故输出2，第四个数被删除，两个小根堆为：{3,5}、{4}。
故输出依次为1、2。
Code: O(N+MlogN) [6324K, 60MS]
// 左偏树 (2018.3.3)
// 洛谷 3377 【模板】左偏树（可并堆）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100005;
inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}
int N, M, a[MAXN], topp = 0;
struct Node{
int val, dist;
Node *lc, *rc, *fa;
bool del;
} pool[MAXN], *nul = pool; // Avoid using NULL
inline void build(int *a, int n){
nul->val = nul->dist = -1, nul->del = 1;
for(register int i = 1; i <= n; i++){
pool[i].val = a[i], pool[i].dist = 0;
pool[i].lc = pool[i].rc = nul, pool[i].fa = &pool[i];
pool[i].del = 0;
}
}
inline Node* find(Node *u) {while(u->fa != u) u = u->fa; return u;}
inline Node* merge(Node *u, Node *v){
if(u == nul) return v;
if(v == nul) return u;
if(u->val == v->val ? u > v : u->val > v->val) swap(u, v);
u->rc = merge(u->rc, v), u->rc->fa = u;
if(u->lc->dist < u->rc->dist) swap(u->lc, u->rc);
u->dist = u->rc->dist + 1;
return u;
}
inline void pop(Node *u){
Node *r = merge(u->lc, u->rc);
r->fa = r, u->del = 1;
}
int main(){
getint(N), getint(M);
for(register int i = 1; i <= N; i++) getint(a[i]);
build(a, N);
for(register int i = 1; i <= M; i++){
int opt, x, y; getint(opt);
if(opt == 1){
getint(x), getint(y);
if(pool[x].del || pool[y].del) continue;
Node *rx = find(&pool[x]), *ry = find(&pool[y]);
if(rx == ry) continue;
merge(rx, ry);
}
else if(opt == 2){
getint(x);
if(pool[x].del) {puts("-1"); continue;}
Node *rx = find(&pool[x]);
printf("%d\n", rx->val);
pop(rx);
}
}
return 0;
}
发表评论