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

很明显这个图是二分图。

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

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

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

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

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

令 $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)$。