「JSOI2011」任务调度

「JSOI2011」任务调度

传送门

一开始还在想写平衡树，看到 \(\text{TRANS}\) 操作后就晓得要用可并堆了。

这题好像就是个可并堆的板子题？？？

• ADD 直接往对应的对里面加元素
• DEC 在对应的堆里面找到这个元素，讨论一下它是不是根节点，然后抠出来重新加进去
• TRANS 合并两个堆
• MIN 查堆顶的值
• WORK 讨论一下根节点和它儿子的大小关系来判 ERROR 的情况，然后就和 DEC 一样了

参考代码：

#include <algorithm>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

    s = 0; int f = 0; char c = getchar();

    while ('0' > c || c > '9') f |= c == '-', c = getchar();

    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

    s = f ? -s : s;

}

const int _ = 502, __ = 300005;

int n, m, q, rt[_];

int fa[__], val[__], dis[__], ch[2][__];

inline int merge(int x, int y) {

    if (!x || !y) return x + y;

    if (val[x] > val[y]) swap(x, y);

    ch[1][x] = merge(ch[1][x], y);

    if (dis[ch[0][x]] < dis[ch[1][x]]) swap(ch[0][x], ch[1][x]);

    dis[x] = dis[ch[1][x]] + 1;

    fa[ch[0][x]] = fa[ch[1][x]] = x;

    return x;

}

inline void update(int x, int y, int z) {

    int f = fa[y], tmp = merge(ch[0][y], ch[1][y]);

    if (f == 0) rt[x] = tmp; else ch[ch[1][f] == y][f] = tmp; fa[tmp] = f;

    fa[y] = ch[0][y] = ch[1][y] = 0, val[y] += z;

    rt[x] = merge(rt[x], y);

}

int main() {

#ifndef ONLINE_JUDGE

    file("cpp");

#endif

    read(n), read(m), read(q);

    char s[10];

    for (rg int x, y, z, i = 1; i <= q; ++i) {

    	scanf("%s", s);

    	if (s[0] == 'A') read(x), read(y), read(z), val[y] = z, rt[x] = merge(rt[x], y);

    	if (s[0] == 'D') read(x), read(y), read(z), update(x, y, -z);

    	if (s[0] == 'T') read(x), read(y), rt[y] = merge(rt[x], rt[y]), rt[x] = 0;

    	if (s[0] == 'M') read(x), printf("%d\n", val[rt[x]]);

    	if (s[0] == 'W') {

    	    read(x), read(y);

    	    if (ch[0][rt[x]] && val[ch[0][rt[x]]] == val[rt[x]]) { puts("ERROR"); continue ; }

    	    if (ch[1][rt[x]] && val[ch[1][rt[x]]] == val[rt[x]]) { puts("ERROR"); continue ; }

    	    update(x, rt[x], y);

    	}

    }

    return 0;

}