题解：P11989 [JOIST 2025] 勇者比太郎 3 / Bitaro the Brave 3

非常好题目，但是不给 $P$ 相等的特殊性质是什么意思？

先考虑对于每个询问做一遍暴力。二分答案，然后按照出现的时间顺序从前往后加入每个怪物，每一时刻选择当前存活的强度最大的怪物进行攻击进行 check。用堆维护可以做到 $\operatorname{O}(nq\log^2n)$。

这个东西看上去没啥前途，不过根据优先选最大攻击的思想可以想到变换顺序，按照强度从大往小填，然后尽可能填满。但每次填入一个数之后要维护有那些位置可以填，这个东西本质是维护连续段并支持合并，显然也无法优化。

上面两种做法都说明了对于单独的一个怪物我们不太能维护出其被攻击的次数，那么不妨整体考虑，求出强度大于等于一个数的怪物整体最多能有多少时间被攻击，然后拆贡献算出答案。即设 $f_i$ 表示排序后 $i\sim N$ 这些怪物总共被攻击多少次，答案为 $\sum_{i=1}^{N}(H_i-H_{i-1}) f_i$。注意这里没有考虑 $H$ 相同的情况，实现过程中可能要写个离散化之类的处理一下。

整理一下想法可以得到一个大致的思路。将怪物按照强度从小到大排序，枚举每一个后缀求出这个后缀中的怪物在每种难度下总共被攻击的次数，然后对每一个后缀将相同难度的贡献合并起来就能得到答案。

现在的问题就是对于保留一段后缀的怪物求出它们最多被攻击的次数。可以发现现在每个怪物被攻击了多少次我们不在乎，所以可以视作它们的强度全部都为 $1$。

考虑解决上面这个问题。将怪物和每个时刻视为两个点集，那么将怪物与能攻击其的时刻连边，求出的答案就是这个二分图的最大匹配。而根据 Hall 定理的推论，将怪物按照出现时间排序，设 $n$ 为当前保留的怪物数量，我们可以得到这个二分图的最大匹配：

这个式子对应到 Hall 定理中有 $|V|=\sum_{j=i}^{n}H_j$，$|n(V)|=T-S_i$。

直接做会得到一个 $\operatorname{O}(N^2L+Q\log L)$ 的东西，考虑优化。

令 $k_i=\sum_{j=i}^{n}H_j,b_i=-T+S_i$，那么上面那个式子就是 $\max_{i=0}^{n}(k_i \ell+b_i)$，即 $n$ 条直线在某个位置的截距最大值。

那么就可以将这些直线拼成一个上凸壳来得到每个 $\ell$ 会受到的贡献。用栈来维护这个凸壳，由于只有 $n$ 条直线，所以凸壳上最多只有 $n$ 个点。用差分分段将这些位置对应的直线加上去就好了。时间复杂度 $\operatorname{O}(N^2+L+Q\log L)$。