P11989
lsj2009
·
·
题解
在 \ell 确定时如何求出最小惩罚分？可以直接构建出费用流模型（其实并不完全是，因为这里要优先最大化费用，但其实后面也说明了，在本题中流量最大化和费用最大化是一致的）！更进一步的，可以模拟费用流（贪心）：从小大扫时间，攻击当前可以攻击的 P_i 最大怪兽。这个模拟费用流过程不涉及任何反悔（也就是能匹配的必然不劣），换言之，我们可以从大到小扫值域 x，取出 P_i\ge x 的所有怪兽，认为所有怪兽 P_i=1 去跑上面的费用流，答案累加。即，x 的匹配方案必然包含 x+1 的匹配方案，由此正确性显然。
对于所有 P_i=1 的问题，费用流直接退化成二分图匹配，根据 Hall 定理，答案就是
\max\limits_{A\subseteq [n]}\left(\ell\sum\limits_{i\in A}
H_i-\left|\bigcup\limits_{i\in A}\left[S_i,T\right]\right|\right)
对 0 取 \max。注意到 |N(A)| 的值仅有 \min\limits_{i\in A}{S_i} 决定，则将所有怪兽按 S_i 从大到小排序后，令 c_i 是 H_i 的前缀和，显然 A 必取一个前缀，答案为 \max\limits_{1\le i\le n}\big(c_i\ell-(T-S_i)\big)。这是一个关于 \ell 的一次函数，直接建出凸包，即可确定 \ell 在每个范围内的答案。要做 n 轮这个过程，求出凸包上每个点的坐标，对以 \ell 为下标的序列 k_i,b_i 做一个区间加，差分即可。复杂度 \mathcal{O}(n^2+L+Q\log{L})。