自动搬运

查看原文

来自洛谷，原作者为

	tzc_wk **

搬运于2025-08-24 22:49:14，当前版本为作者最后更新于2023-08-12 22:08:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先显然可以 $n^2\log n$ 地贪心。但是没法优化。

注意到这个模型等价于二分图最大匹配，考虑特殊二分图模型的重要工具：霍尔定理，具体来说一张二分图假设左部点集合为 $A$，右部点集合为 $B$，那么最大匹配就是 $|A|-\max\limits_{S\subseteq A}\{|S|-|\text{Nb}(S)|\}$。应用到此题上就是红点个数 $-\max\limits_{\{[l_i,r_i]\}\text{两两不相交}}\sum\limits_{i=1}^k\text{sumred}(l_i,r_i)-\text{sumblue}(l_i-L,r_i+L)$。其中要求相邻区间间隔 $>2L$，否则把间隔 $\le 2L$ 的并起来肯定是更优的。

考虑如何求这个东西，记 $R_i$ 和 $B_i$ 为红点个数的前缀和，然后记 $p_i=-R_{i-1}+B_{l_i-L-1},q_i=R_i-B_{i+L}$，那么这个问题等价于间隔选 $p,q,p,q$ 的最大权值和，线段树维护一下，记 $f_{i,0/1,0/1}$ 表示线段树 $i$ 节点，以 $p/q$ 开始，以 $p/q$ 结束的最大权值和，合并可以 $O(1)$。

考虑修改的贡献：

• 加入红点等价于 $[x+1,\infty)$ 的 $p$ 减去 $v$，$[x,\infty)$ 的 $p$ 加上 $v$，注意到区间加好像有点难维护，但是对于一个区间的 $p$ 加 $v$，$q$ 减 $v$，对于固定的 $x,i,j$，$f_{x,i,j}$ 的最优策略是不变的，因为它会加多少个 $p$ 已经在 $i,j$ 中有所体现。因此可以直接打 tag，这样加入红点的贡献等价于区间加 + 单点修改。
• 加入蓝点等价于 $[x+L+1,\infty)$ 的 $p$ 加上 $v$，$[x-L,\infty)$ 的 $p$ 减去 $v$，还是将修改拆成一段 $p$ 加 $q$ 减，不过这次剩的是区间加。发现一个性质是这个区间长度 $\le 2L$，根据间隔 $>2L$ 的性质可以对每一类 $f_{i,0/1,0/1}$ 算出它里面究竟有多少个 $q$，这样标记就是可加的了。

时间复杂度 $n\log n$。