CF1895G 题解

· · 题解

要求最大化收益加上支出，又因为每个字符有染红和染蓝两种选择，考虑最小割模型。可以看成是一开始先获得 r_i + b_i 的收益，然后对于每个 0，连边 (S, i, b_i), (i, T, r_i)；对于每个 1，连边 (S, i, r_i), (i, T, b_i)；每个 1 向它后面的所有 0 连容量为 1 的边。然后 \sum r_i + b_i 减去最小割即为答案。

很可惜边数是 O(n^2) 的，没办法直接跑最大流。观察这个网络流图，发现它长得比较好看，于是可以尝试模拟最大流。

我们首先有一个显然的流量下界 \sum \min(r_i, b_i)。我们先让每个点流过 \min(r_i, b_i) 的流量。对于一个 1，源点流向它的 k_i = r_i - \min(r_i, b_i) 的流量被浪费了。我们尝试把这些流量往后面的 0 流。那么对于一个 0，它还能往汇点流 k_i 的流量。要从前面的 1 获取一些流量。我们贪心地在前面剩余流量前 k_i 大的 1 获取 1 的流量，正确性证明大概就是选择其他的 1 获取流量不会变优。

于是我们遇到一个 1 就往剩余流量可重集里加入 k_i，遇到一个 0 就把这个集合的前 k_i 大元素减 1，然后剔除掉值为 0 的元素。多的流量就是每次遇到 0 时，集合内实际被减了 1 的元素数量之和。

那么现在需要一个数据结构，支持：

使用 FHQ Treap 维护即可。前 k 大元素减 1 的操作，可以先分裂成 x, y 两棵子树使得 x 大小为 sz_{rt} - k，y 大小为 k；然后如果 x 子树内最大值小于 y 子树内最小值，就可以直接打个 tag 把 y 子树内的全部值减 1；否则继续分裂，设此时 x 子树内最大值为 t，把 x 分成值 < t 和值 = t 两部分，y 分成值 = t 和值 > t 两部分，把 y 的两部分分别打 tag 减 1 后再依次合并即可。

时间复杂度 O(n \log n)。

code