rockdu
题目描述
如题，初始小根堆为空，我们需要支持以下3种操作：
操作1： 1 x 表示将x插入到堆中
操作2： 2 输出该小根堆内的最小数
操作3： 3 删除该小根堆内的最小数
输入输出格式
输入格式：
第一行包含一个整数N，表示操作的个数
接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：
操作1： 1 x
操作2： 2
操作3： 3
输出格式：
包含若干行正整数，每行依次对应一个操作2的结果。
输入输出样例
输入样例#1：
5 1 2 1 5 2 3 2
输出样例#1：
2 5
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=15
对于70%的数据：N<=10000
对于100%的数据：N<=1000000（注意是6个0。。。不过不要害怕，经过编者实测，堆是可以AC的）
样例说明：
故输出为2、5
直到今天我才发现，我用了太久priority_queue，都写不来堆了。于是今天写了一发。
结果日常刷洛谷评测机，呵呵……
所以一定要处理好条件，否则会爆炸的。
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<queue>
#include<cmath>
using namespace std;
const int maxn = 1e6 + 100;
inline void read(int & x) {
x = 0; char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) x = (x << 1) + (x << 3) + c - '0', c = getchar();
}
int pt[30], cnt;
inline void put(int x) {
if(!x) {putchar('0'), putchar('\n');return;}
while(x) pt[++cnt] = x % 10, x /= 10;
while(cnt) putchar(pt[cnt--] + '0');
putchar('\n');
}
namespace Fib_Heap {
struct node {
int l, r, fa, ch;
int key, degree;
void clr() {l = r = fa = ch = degree = 0;}
}tree[maxn];
int mnnode, cnt, n, D = 5;
queue<int > mempool;
#define rtl_init(rt) (tree[rt].l = tree[rt].r = rt)
inline int top() {return tree[mnnode].key;}
void add_after(int org, int rt) {
tree[rt].r = tree[org].r;
tree[org].r = rt;
tree[tree[rt].r].l = rt;
tree[rt].l = org;
}
inline void remove(int rt) {
tree[tree[rt].l].r = tree[rt].r;
tree[tree[rt].r].l = tree[rt].l;
}
inline void del(int rt) {
tree[tree[rt].l].r = tree[rt].r;
tree[tree[rt].r].l = tree[rt].l;
tree[rt].l = tree[rt].r = rt;
}
void linkto(int x, int y) {
tree[x].fa = y, remove(x), ++tree[y].degree;
if(tree[y].ch) add_after(tree[y].ch, x);
else rtl_init(x), tree[y].ch = x;
}
void push(int x) {
++n;int now;
if(!mempool.empty())
tree[now = mempool.front()].clr(), tree[mempool.front()].key = x, mempool.pop();
else tree[now = ++cnt].key = x;
if(!mnnode) mnnode = now, rtl_init(now);
else {
add_after(mnnode, now);
if(x < tree[mnnode].key)
mnnode = now;
}
}
void combine() {
D = (int)log(n) + 5;
int a[D] = { };
int now = mnnode, nxt = 1, ant;
while(nxt) {
int d = tree[now].degree;
nxt = tree[now].r == now ? 0 : tree[now].r, del(now);
while(a[d]) {
ant = a[d];
if(tree[now].key > tree[ant].key)
swap(now, ant);
linkto(ant, now);
a[d] = 0, ++d;
}
a[d] = now, now = nxt;
};
mnnode = 0;
for(register int i = 0; i < D; ++i) {
if(!a[i]) continue;
if(!mnnode) mnnode = a[i], rtl_init(a[i]);
else {
add_after(mnnode, a[i]);
if(tree[a[i]].key < tree[mnnode].key)
mnnode = a[i];
}
}
}
void pop() {
if(!mnnode) return;
int st = tree[mnnode].ch;
int now = st;
register int nxt;
if(st)
do {
nxt = tree[now].r;
add_after(mnnode, now);
now = nxt;
} while(now ^ st);
remove(mnnode), mempool.push(mnnode);
if(mnnode == tree[mnnode].r) mnnode = 0;
else mnnode = tree[mnnode].r, combine();
--n;
}
};
int main() {
using namespace Fib_Heap;
int t, m;
read(m);
while(m--) {
read(t);
if(t == 1) read(t), push(t);
else if(!(t & 1)) put(top());
else pop();
}
return 0;
} ##2017-10-22
今天比较闲，随手写了一个斐波那契堆交上去。结局是跑的比stl还慢，我可能学了个假的斐堆……
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cmath>
using namespace std;
const int maxn = 2e5 + 5;
inline void read(int & x) {
x = 0; char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) x = (x << 1) + (x << 3) + c - '0', c = getchar();
}
int pt[30], tot;
inline void put(int x) {
if(!x) {putchar('0'), putchar('\n');return;}
while(x) pt[++tot] = x % 10, x /= 10;
while(tot) putchar(pt[tot--] + '0');
putchar('\n');
}
int p[maxn];
int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);}
int comto(int x, int rt){p[find(x)] = rt;}
namespace Fib_Heap {
struct node {
int l, r, fa, ch;
int key, degree;
}tree[maxn];
int cnt, D = 5;
int rtn[maxn], deled[maxn];
#define rtl_init(rt) (tree[rt].l = tree[rt].r = rt)
inline int top(const int &rt) {return tree[rt].key;}
void add_after(int org, int rt) {
tree[rt].r = tree[org].r;
tree[org].r = rt;
tree[tree[rt].r].l = rt;
tree[rt].l = org;
}
inline void remove(int rt) {
tree[tree[rt].l].r = tree[rt].r;
tree[tree[rt].r].l = tree[rt].l;
}
inline void del(int rt) {
tree[tree[rt].l].r = tree[rt].r;
tree[tree[rt].r].l = tree[rt].l;
tree[rt].l = tree[rt].r = rt;
}
void linkto(int x, int y) {
tree[x].fa = y, remove(x), ++tree[y].degree;
if(!tree[y].ch) rtl_init(x), tree[y].ch = x;
else add_after(tree[y].ch, x);
}
void push(int rt, int x) {
tree[++cnt].key = x, ++rtn[rt];
if(!rt) rt = cnt, rtl_init(cnt);
else {
add_after(rt, cnt);
if(x < tree[rt].key)
rt = cnt;
}
}
void combine(int rt) {
D = (int)log(rtn[rt]) + 5;
int a[D] = { };
int now = rt, nxt = 1, ant;
while(nxt) {
int d = tree[now].degree;
nxt = tree[now].r == now ? 0 : tree[now].r, del(now);
while(a[d]) {
ant = a[d];
if(tree[now].key > tree[ant].key)
swap(now, ant);
linkto(ant, now);
a[d] = 0, ++d;
}
a[d] = now, now = nxt;
};
rt = 0;
for(register int i = 0; i < D; ++i) {
if(!a[i]) continue;
if(!rt) rt = a[i], rtl_init(a[i]);
else {
add_after(rt, a[i]);
if(tree[a[i]].key < tree[rt].key)
rt = a[i];
}
}
}
void pop(int rt) {
if(!rt) return;
int st = tree[rt].ch;
int now = st;
register int nxt;
if(st)
do {
nxt = tree[now].r;
add_after(rt, now);
now = nxt;
} while(now != st);
remove(rt);
if(rt == tree[rt].r) rt = 0;
else rt = tree[rt].r, combine(rt);
--rtn[rt];
}
void Union(int rt1, int rt2) {
int nd1 = tree[rt1].l, nd2 = tree[rt2].r;
tree[rt1].l = rt2;
tree[rt2].r = rt1;
tree[nd1].r = nd2;
tree[nd2].l = nd1;
}
};
int main() {
using namespace Fib_Heap;
int t, n, m, a;
read(n), read(m);
for(register int i = 1; i <= n; ++i) p[i] = i;
for(register int i = 1; i <= n; ++i)
read(a), rtn[i] = 1, push(i, a);
while(m--) {
read(t);
if(t == 1) {
read(a), read(t);
int rt1 = find(a), rt2 = find(t);
if(rt1 == rt2 || deled[a] || deled[t]) continue;
Union(rt1, rt2);
if(tree[rt1].key > tree[rt2].key) comto(rt1, rt2), rtn[rt2] += rtn[rt1];
else comto(rt2, rt1), rtn[rt1] += rtn[rt2];
}else {
read(a);
if(deled[a]) {put(-1); continue;}
a = find(a);
put(top(a)), deled[a] = 1, pop(a);
}
}
return 0;
}
没有帐号? 立即注册