左偏树模板
左偏树 (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; }
发表评论