标签：

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

「JSOI2011」任务调理