题解：P9104 [PA 2020] Królewski bal

reinforest · 2025-11-19 20:00:29 · 题解

很明显这个图是二分图。

有结论：二分图最大匹配数=二分图最小点覆盖=总点数-二分图最大独立集点数。

考虑求出二分图最大独立集。

对于“最大独立集”，我们需要有以下的限制：

我们选择的“黑色点”以及“白色点”不能同时在一行或者一列。

这相当于我们钦定了“每一行”的颜色和“每一列”的颜色，然后只需要考虑交叉部分的颜色。

令 a_i 表示第 i 列有多少个白色节点，令 b_i 表示第 i 行有多少黑色节点，不妨先随便枚举集合 S，如果 x \in S 表示我们选择了第 x 列为白色。

然后我们考虑怎么样选择集合 T（表示我们选择黑色的行），初始我们全部都选择白色，考虑增量对答案的贡献，这样我们取最大值就是我们想要的“最大独立集”。

现在考虑加入一行 y，考虑第 x 列的贡献，分类讨论：

仅有 2 类点和 3 类点会对答案造成贡献，2 类点有 +1 的贡献，3 类点有 -1 的贡献。

设 W_i 表示第 i 行在 S 中有多少白色格子，B_i 表示第 i 行在 S 中有多少黑色格子，那么有 W_i+B_i=S，贡献和为 (b_i-B_i)-W_i=b_i-|S|。

所以 S 的具体取值并不会影响最终的答案，我们记 x=|S|，那么对于固定的 x 的答案就是，\sum\limits_{i=1}^x A_i+\sum\limits_{i=1}^n\max(0,b_i-x)，定义 A_i 为 a_i 从大到小排序后的数组。

可以定义函数 F(x)=\sum\limits_{i=1}^x A_i+\sum\limits_{i=1}^n\max(0,b_i-x)。我们仅需要快速求出 a_i,b_i 以及维护单点修改就行，询问实际上就是 n^2-\max\limits_{i=\color{red}{0}}^n F(i)。

快速求出 a_i,b_i 可以扫描线。维护一个线段树支持区间翻转，区间求 1 或者 0 的个数的线段树就行。

维护这个函数，也需要考虑线段树，维护区间修改，全局查最大值。

可以分别考虑 a_i,b_i 的变化，由于 a_i,b_i 仅能 \pm 1，可以考虑 a_i,b_i 的贡献区间。

对于一个 b_i 来讲，其实能够贡献的 x 在 [0,b_i-1] 中。当 b_i 变化的时候，在对应区间 \pm 1 即可。

对于一个 a_i 来讲，其实 \pm 1 相当于改变了这个数在原数组中对应的位置，可以维护每一个值 x 在线段树上对应的区间 l_x,r_x。当 a_i 加 1 时，a_i 会向左移，令 x 为原来的 a_i，可以让 l_x 加一，r_{x+1} 加一。那么 a_i 向右移的情况是一样的。

时间复杂度 O(n \log n)。