题解 P3377 【【模板】左偏树(可并堆)】
Creeper_LKF
2017-12-27 19:08:37
于是我们这次迎来了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;
}
```