【???】???

from 神/se

题面

有 $n$ 个箱子排成一行，第 $i$ 个箱子里最多能装 $a_i$ 个球。

还有 $m$ 个人，第 $i$ 个人手里有 $c_i$ 个球，并且可以往编号在 $[l_i,r_i]$ 中的箱子放球。

每个人还有一个类型 t i ∈ { 0 , 1 } t_i\in\{0,1\} ti​∈{0,1}。

对 $x=1,\cdots ,n$ 求出：若将所有 $t_i=1$ 的人的限制范围改成 $l_i^{\prime }=\min (x,l_i)$，$r_i^{\prime }=\max (r_i,x)$，那么最多能放多少个球。

$n,m\le 2\times 10^5$，$a_i,c_i\le 10^9$。

题解

若 $t_i$ 全等于 $0$，相当于左边每个点能匹配右边一个区间的二分图匹配问题，贪心即可做到 $O(n\log n)$：从小到大枚举右边的所有点 $x$，过程中将 $l\le x$ 的所有区间加入一个堆中，堆顶是 $r$ 最小的，那么每次 $x$ 肯定优先匹配堆顶。

但对于这题，我们考虑利用 Hall 定理求解，答案可表示为：
∑ i = 1 m c i − max ⁡ S ⊆ { 1 , ⋯   , n } ( c ( S ) − N ( S ) ) \sum_{i=1}^{m}c_i-\max_{S\subseteq\{1,\cdots,n\}}(c(S)-N(S)) i=1∑m​ci​−S⊆{1,⋯,n}max​(c(S)−N(S))
$N(S)$ 表示 $S$ 能放的箱子的 $a_i$ 之和。

注意到 $N(S)$ 一定是若干段两两不交的区间构成，加上一个新的不交的区间 $[L,R]$ 会使权值加上所有 $[l_i,r_i]$ 在 $[L,R]$ 内部的 $c_i$ 再减去 ${\sum }_{j=L}^R{a}_j$。

设 $pr{e}_i$ 表示只考虑那些 $t_j=0$ 的人，且 $N(S)$ 在 $[1,i]$ 范围内的 max ⁡ S ⊆ { 1 , ⋯   , n } ( c ( S ) − N ( S ) ) \max\limits_{S\subseteq\{1,\cdots,n\}}(c(S)-N(S)) S⊆{1,⋯,n}max​(c(S)−N(S))。同理设 $su{f}_i$。

使用线段树对每个 $j$ 维护 $pr{e}_{j-1}+C[j,i]-N(j,i)$ 即可 $O(n\log n)$ 计算 $pre$ 和 $suf$，其中 $C[L,R]$ 表示所有 $[l_i,r_i]$ 在 $[L,R]$ 内部的 $c_i$ 之和。

现在考虑对于某 $x$ 计算答案。考虑 $S$ 中 $t_i=1$ 的那些区间，它们肯定都在 $N(S)$ 中同一个包含 $x$ 的区间内，那么答案为：
$$\sum _{i=1}^m{c}_i-\underset{L\le x\le R}{\max }(C[L,R]-\sum _{i=L}^R{a}_i+pr{e}_{L-1}+su{f}_{R+1})$$
考虑分治。计算跨过 $mid$ 的区间 $[L,R]$ 对 $x$ 的贡献，其中 $L_{\lim }\le L$ 且 $R\le R_{\lim }$。

具体地，计算 $f_L$ 表示 $\underset{R\in [mid+1,R_{\lim }]}{\max }(C[L,R]-{\sum }_{i=L}^R{a}_i+pr{e}_{L-1}+su{f}_{R+1})$，然后对每个 $x\in [L_{\lim },mid]$ 用 $\underset{L\in [L_{\lim },x]}{\max }{f}_L$ 更新。对于 $x\in [mid+1,R_{\lim }]$ 的更新同理。

记 $g_R=\left(C[L,R]-{\sum }_{i=L}^R{a}_i+pr{e}_{L-1}+su{f}_{R+1}\right)$。那么随着 $L$ 变小，我们要做的是对 $g_R$ 后缀加以及问 $g_R$ 全局 $\max$。

注意到总共只会有 $O(n)$ 次 $g_R$ 的后缀加（每个区间 $[l_i,r_i]$ 只会在跨过 $mid$ 时贡献一次），那么直接用线段树维护即可。总时间复杂度 $O(n\log n)$。