P11989

在 $\ell$ 确定时如何求出最小惩罚分？可以直接构建出费用流模型（其实并不完全是，因为这里要优先最大化费用，但其实后面也说明了，在本题中流量最大化和费用最大化是一致的）！更进一步的，可以模拟费用流（贪心）：从小大扫时间，攻击当前可以攻击的 $P_i$ 最大怪兽。这个模拟费用流过程不涉及任何反悔（也就是能匹配的必然不劣），换言之，我们可以从大到小扫值域 $x$，取出 $P_i\ge x$ 的所有怪兽，认为所有怪兽 $P_i=1$ 去跑上面的费用流，答案累加。即，$x$ 的匹配方案必然包含 $x+1$ 的匹配方案，由此正确性显然。

对于所有 $P_i=1$ 的问题，费用流直接退化成二分图匹配，根据 Hall 定理，答案就是

对 $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})$。