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

2017-12-27 19:08:37


于是我们这次迎来了pbds的priority_queue(话说最近一直在写这个)

于是在有join(merge)的情况下应该是跑的更快的。

这里我们选择标签pairing_heap_tag,因为它的push和join操作是O(1)的(不知为何楼下的写的pairing_heap_tag常数大...68ms)。

然后根据题面描述注意operator的定义,然后pbds堆的定义的符号是反的。

同时在外面我们用并查集辅助找到堆。

#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;

}//在处理重复数据的时候需要这个板子(此题可以标记堆的位置)

    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;
}