题解 P3377 【【模板】左偏树(可并堆)】

Creeper_LKF

2017-12-27 19:08:37

Solution

于是我们这次迎来了pbds的priority\_queue(话说最近一直在写这个) 于是在有join(merge)的情况下应该是跑的更快的。 这里我们选择标签pairing\_heap\_tag,因为它的push和join操作是O(1)的(不知为何楼下的写的pairing\_heap\_tag常数大...68ms)。 然后根据题面描述注意operator的定义,然后pbds堆的定义的符号是反的。 同时在外面我们用并查集辅助找到堆。 ```cpp #include <cstdio> #include <cctype> #include <ext/pb_ds/priority_queue.hpp> using namespace std; using namespace __gnu_pbds; #define MAXN 100005 inline char get_char(){ static char buf[5000001], *p1 = buf, *p2 = buf + fread(buf, 1, 5000000, stdin); return p1 == p2 ? EOF : *p1 ++; } inline int read(){ int num = 0; char c, sf = 1; while (isspace(c = get_char())); if(c == '-') sf = -1, c = get_char(); while (num = num * 10 + c - 48, isdigit(c = get_char())); return num * sf; } int father[MAXN]; inline int Get_Father(int u){ return father[u] == u ? u : father[u] = Get_Father(father[u]); } struct Node{ int v, id; Node(int a, int b){ v = a, id = b; ``` }//在处理重复数据的时候需要这个板子(此题可以标记堆的位置) ```cpp bool operator < (Node tar) const { return v == tar.v ? id > tar.id : v > tar.v;//priority需要反向定义,注意题中大小定义要求 } }; typedef __gnu_pbds::priority_queue<Node, less<Node>, pairing_heap_tag> Heap; Heap stl_heap[MAXN]; Heap::iterator itx, ity; bool del[MAXN]; int main(){ int n = read(), m = read(); for(int i = 1; i <= n; i++){ Node data(read(), i); father[i] = i; stl_heap[i].push(data); } for(int i = 1; i <= m; i++){ int cons = read(); if(cons & 1){ int x = read(), y = read(), fx = Get_Father(x), fy = Get_Father(y); if(fx == fy || del[x] || del[y]) continue; stl_heap[fx].join(stl_heap[fy]); father[fy] = fx; } else { int x = read(), fx = Get_Father(x); if(del[x] || stl_heap[fx].empty()) puts("-1"); else { Node data = stl_heap[fx].top(); stl_heap[fx].pop(); del[data.id] = true; printf("%d\n", data.v); } } } return 0; } ```