题目地址：BZOJ：Problem 5179. — [Jsoi2011]任务调度

题目描述

一台超级计算机共有N颗CPU。现在这台超级计算机有M个任务要做，但同时还要考虑到不能让CPU过热。所幸的是这台超级计算机已经将任务安排好了，现在要做的只是请你根据安排好的指令来模拟它的工作过程。一开始，这N颗CPU都没有被分配任何的任务。之后，会给你以下几类指令（CPU的编号为1到N的整数，任务的编号为1到M的整数）
指令格式 作用
ADD n k w 将 k 号任务（权值为 w）分配给 n 号 CPU
DEC n k w 将 k 号任务的权值减少 w（已知 k 号任务被分配给了 n 号 CPU）
TRANS n1 n2 将分配给 n1 号 CPU 的任务全部转移给 n2 号 CPU
MIN n 输出分配给 n 号 CPU 的任务中权值最小的任务的权值
WORK n w 将分配给 n 号 CPU 的任务中权值最小的任务的权值加上 w，如果权值最小的任务不唯一，则不更改权值，并输出一行“ ERROR”

输入输出格式

输入格式：
包含N+1行。
第1行包含三个正整数N、M、K，分别表示CPU的数目、任务数和指令数。
第2行到K+1行，每行包含一条指令。
N≤500， M≤300000， K≤300000。
保证任务的权值在 32 位有符号整型的范围内。
保证一个任务只会被分配一次（即至多被 ADD 一次）。
保证 ADD 指令、DEC 指令和 WORK 指令中的 w 是非负整数。
保证 TRANS 指令的两个参数不相同。

输出格式：
若干行，其中包括MIN语句的输出和“ERROR”输出，每个输出占一行

输入输出样例

输入样例#1：

2 3 13
ADD 1 2 100
ADD 1 1 90
MIN 1
WORK 1 20
TRANS 1 2
MIN 2
ADD 1 3 105
TRANS 2 1
MIN 1
DEC 1 3 200
MIN 1
DEC 1 1 205
WORK 1 15

输出样例#1：

90
100
100
-95
ERROR

题解

考虑左偏树来做这个题。ADD即新建节点并且合并到该CPU堆。DEC即先删点，改完权值以后再并回去。TRANS即合并两个堆。MIN即询问堆中最小值。WORK同DEC。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline char readop() {
    char c;
    while(!isalpha(c = fgc()));
    return c;
}

const int MAXN = 300005;

struct Node {
    int fa, val, dis, ch[2];
} tr[MAXN];

inline int merge(int u, int v) {
    if(!u || !v) return u + v;
    if(tr[u].val > tr[v].val) std::swap(u, v);
    tr[u].ch[1] = merge(tr[u].ch[1], v);
    tr[tr[u].ch[1]].fa = u;
    if(tr[tr[u].ch[0]].dis < tr[tr[u].ch[1]].dis) std::swap(tr[u].ch[0], tr[u].ch[1]);
    tr[u].dis = tr[tr[u].ch[1]].dis + 1;
    return u;
}

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline void erase(int p) {
    tr[tr[p].ch[0]].fa = tr[tr[p].ch[1]].fa = 0;
    int q = merge(tr[p].ch[0], tr[p].ch[1]);
    if(q) tr[q].fa = tr[p].fa; if(tr[p].fa) tr[tr[p].fa].ch[!isleft(p)] = q;
    for(int i = tr[p].fa; i; i = tr[i].fa) {
        if(tr[tr[i].ch[0]].dis < tr[tr[i].ch[1]].dis) std::swap(tr[i].ch[0], tr[i].ch[1]);
        if(tr[i].dis == tr[tr[i].ch[1]].dis + 1) break;
        tr[i].dis = tr[tr[i].ch[1]].dis + 1;
    }
    tr[p].fa = tr[p].ch[0] = tr[p].ch[1] = tr[p].dis = 0;
}

inline int poprt(int p) {
    tr[tr[p].ch[0]].fa = tr[tr[p].ch[1]].fa = 0;
    int q = merge(tr[p].ch[0], tr[p].ch[1]);
    tr[p].fa = tr[p].ch[0] = tr[p].ch[1] = tr[p].dis = 0;
    return q;
}

int n, m, k, x, y, z, rt[MAXN];
char op;

int main() {
    tr[0].dis = -1;
    n = readint(); m = readint(); k = readint();
    while(k--) {
        op = readop();
        if(op == 'A') {
            x = readint(); y = readint(); z = readint();
            tr[y].val = z;
            rt[x] = merge(y, rt[x]);
        } else if(op == 'D') {
            x = readint(); y = readint(); z = readint();
            if(!tr[y].fa) rt[x] = poprt(y);
            else erase(y);
            tr[y].val -= z;
            rt[x] = merge(rt[x], y);
        } else if(op == 'T') {
            x = readint(); y = readint();
            rt[y] = merge(rt[x], rt[y]);
            rt[x] = 0;
        } else if(op == 'M') {
            x = readint();
            printf("%d\n", tr[rt[x]].val);
        } else {
            x = readint(); y = readint(); int p = rt[x];
            if((tr[p].ch[0] && tr[tr[p].ch[0]].val == tr[p].val)
                || (tr[p].ch[1] && tr[tr[p].ch[1]].val == tr[p].val)) {
                puts("ERROR");
                continue;
            }
            rt[x] = poprt(p);
            tr[p].val += y;
            rt[x] = merge(rt[x], p);
        }
    }
    return 0;
}