题解 P9528 [JOISC 2022 Day3] 蚂蚁与方糖

tzc_wk · 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。