补全证明：棋盘格子配对问题

一、从格子配对到二分图最大匹配

1. 图模型

当前棋盘是 $n \times n$ 的，每个格子要么黑要么白。我们要选出若干对格子 $((x_1,y_1),(x_2,y_2))$，满足：

$(x_1,y_1)$ 是白，$(x_2,y_2)$ 是黑；
在同一行或同一列；
每个格子最多被用一次。

用图论语言建模：

把所有白格子作为二分图左部的点；
把所有黑格子作为二分图右部的点；
如果一个白格子和一个黑格子在同一行或同一列，就在它们之间连一条边。

那么：

一条边对应一个合法的格子对（白 → 黑）。
一组互不相交的边（没有公共端点）对应一组互不相交的格子对。

因此： 要选的格子对数量 = 这个二分图的最大匹配大小。

这就证明了“答案即为二分图最大匹配”的那一步。

二、从最大匹配到最大独立集

一个小知识：在任意图中，有如下关系： $$ \text{最大独立集大小} + \text{最小点覆盖大小} = |V| $$ 其中 $|V|$ 为点数。

在二分图中还有著名的 Kőnig 定理：

在任何二分图中： 最大匹配大小 = 最小点覆盖大小。

于是对我们这个二分图： $$ \text{最大匹配} = \text{最小点覆盖} = |V| - \text{最大独立集} $$

本题中点就是所有格子，数量为 $n^2$。于是： $$ \text{答案} = \text{最大匹配大小} = n^2 - \text{最大独立集大小} $$

所以求最大匹配 ⇔ 求最大独立集，求后者更方便做结构分析。

三、最大独立集在棋盘上的结构

回忆一下图的定义：

点：每个格子（带颜色）；
边：同一行或同一列中，颜色不同的一对格子。

独立集：点集 $I$，其中任意两点之间没有边。也就是：不会出现同一行 / 列中同时选了一个黑格子和一个白格子。

1. 每行每列只能选一种颜色 —— 证明

结论： 在任意一个独立集中，对每一行 / 每一列：

如果这一行（列）里被选的格子不是空的，那么它们的颜色都相同。

证明：

反设某一行 $x$ 中，在独立集里同时选了一个黑格子 $(x,y_1)$ 和一个白格子 $(x,y_2)$。
按图的定义：只要「同一行且颜色不同」就有一条边。
所以 $(x,y_1)$ 与 $(x,y_2)$ 之间有边。
但独立集中任意两点之间不能有边，矛盾。

同理，对列也是一样。

所以： 最大独立集在原方阵中的形态：每一行 / 每一列中选的格子只会有一种颜色。

这就补上了题解里那句 “形态” 的严谨理由。

四、用集合 $S,T$ 描述独立集

根据上面的结构，我们可以这样编码一个独立集：

对每一行，决定：这行“如果选格子的话”，是选黑还是选白；
对每一列，也做同样的决定。

我们用两个集合来表示“选白”的行列：

集合 $T$：表示选择白色的行；
集合 $S$：表示选择白色的列。

于是：

行 $x \in T$：这一行里若有选中的格子，则只能选 白格子；
行 $x \notin T$：这一行里若有选中的格子，则只能选 黑格子；
列 $y \in S$：这一列里若有选中的格子，则只能选 白格子；
列 $y \notin S$：这一列里若有选中的格子，则只能选 黑格子。

把行和列的选择合在一起，一个格子 $(x,y)$ 能被选，当且仅当：

若它是白色：行、列都选择白：$x \in T, y \in S$；
若它是黑色：行、列都选择黑：$x \notin T, y \notin S$。

我们把这两类格子全部选上，就能得到一个独立集，而且显然是在固定 $(S,T)$ 下数量最多的独立集（因为所有合法格子都选了）。

所以对每一组 $(S,T)$，最大独立集大小就是：

白格子且 $x\in T, y\in S$ 的个数

加上黑格子且 $x\notin T, y\notin S$ 的个数。

题解中对应那句：

对于点 $(x, y)$：

若目前为白且 $x \in T, y \in S$，贡献 $1$；

若目前为黑且 $x \notin T, y \notin S$，贡献 $1$。

至此，“枚举 $S,T$” 这一段就完全合理了。

五、关键观察：行贡献只和 $|S|$ 有关

题解接下来做了一个非常关键的“降维观察”：

先只枚举列的选择，把“哪些列选白”设为集合 $S$；
初始先假定“所有行都选白”（即 $T = \{1,\dots,n\}$）；
然后再考虑某些行从“选白”变成“选黑”的收益。

1. 基础方案：所有行选白

设：

每列 $j$ 的白格子数为 $a_j$。

当所有行都选白（$T=\{1,\dots,n\}$）时：

对于列 $j\in S$：行、列都选白，所以所有的白格子都可以被选；
对于列 $j\notin S$：列选黑，这里没有格子同时满足“行、列都白”。

于是此时独立集的大小是： $$ \text{Base}(S) = \sum_{j \in S} a_j $$

这就是题解里的那句：

设集合 $S$ 中的列选了白，所有行都选了白。贡献为 $S$ 列中白格子个数。

2. 把某一行从“白行”改为“黑行”的增量贡献

重点：我们在固定 $S$ 的前提下，看某一行改色对答案的影响。

设这一行是第 $i$ 行：

这一行的黑格子数为 $b_i$；
这一行总共 $n$ 个格子。

我们考虑这一行由“选白”（在 $T$ 中）变为“选黑”（不在 $T$ 中）时，独立集大小变化多少。

把这一行里的格子拆成 4 种情况（按颜色 + 所在列是否在 $S$）：

情况 1：白格子，并且所在列在 $S$。
- 在“行白、列白”时：行、列都选白 → 这个白格子被选中。
- 在“行黑、列白”时：行选黑、列选白 → 白格子不再能被选中。
这类格子：每个**-1**。
情况 2：白格子，并且所在列不在 $S$。
- “行白、列黑”：此时这个白格子不能被选（列选黑）；
- “行黑、列黑”：行也黑了，还是不能选白格子。
→ 这类格子对答案无影响，贡献 0。
情况 3：黑格子，并且所在列在 $S$。
- “行白、列白”：显然不能选黑格子；
- “行黑、列白”：依然不能选黑格子（列不是黑）。
→ 这类格子贡献 0。
情况 4：黑格子，并且所在列不在 $S$。
- “行白、列黑”：行选白，这个黑格子不能选；
- “行黑、列黑”：行、列都选黑，这个黑格子可以选！
→ 每个贡献 +1。

把这四种情况放在一起：

本来被选的：只有情况 1；
修改后被选的：只有情况 4；

所以这一行净变化 = $$ \text{（情况 4 的个数）} - \text{（情况 1 的个数）} $$

设：

这一行在列 $S$ 中的黑格子数为 $B_S$；
在列 $S$ 中的白格子数为 $W_S$；

则：

“情况 1 的个数” = $W_S$；
“情况 4 的个数” = 这一行不在 $S$ 中的黑格子数 = 总黑格子数 $b_i$ 减去在 $S$ 中的黑格子数 $B_S$： $$ \text{情况 4 个数} = b_i - B_S $$

于是净贡献： $$ \Delta_i = (b_i - B_S) - W_S = b_i - (B_S + W_S) $$

注意到：

一行里在列 $S$ 中一共有 $|S|$ 个格子；
它们要么是黑要么是白，所以 $B_S + W_S = |S|$。

于是： $$ \boxed{\Delta_i = b_i - |S|} $$

这个式子里已经没有 “$S$ 中哪些具体列” 的信息了，只剩下 $|S|$！

这正是题解中那句 “惊人结论” 的严密证明：

一行从白变黑对答案的贡献是： 行内黑格子数 $b_i$ 减去白列数 $|S|$。因此贡献和 $S$ 的具体内容无关，只和 $|S|$ 有关。

3. 对整张棋盘的贡献

在固定列集合 $S$ 的前提下：

基础方案（所有行选白）贡献：$\sum_{j\in S} a_j$；
对于每一行 $i$，如果把它从白改黑有正收益 $\Delta_i = b_i-|S|>0$，我们就把这一行改成黑行；否则就保持白行不动。

于是整张图在给定 $S$ 时的最大独立集大小为： $$ \text{MIS}(S) = \sum_{j\in S} a_j + \sum_{i=1}^{n} \max(0, b_i - |S|) $$

设 $|S| = x$，可以写成： $$ \text{MIS}(S) = \sum_{j\in S} a_j + \sum_{i=1}^{n} \max(0, b_i - x) $$

对于固定的 $x$（即固定的 $|S|$），第二项只跟 $x$ 有关，与具体的 $S$ 无关；第一项要让 $\sum_{j\in S} a_j$ 最大，只要选出“白格子数最多的 $x$ 列”。

六、排序列得到最终公式

记：

对所有列的白格子数 $a_1,\dots,a_n$ 按降序排序，得到 $A_1 \ge A_2 \ge \dots \ge A_n$。

对于给定的 $x = |S|$，最优的列集合是取白格子最多的前 $x$ 列，因此 $$ \max_{|S| = x} \sum_{j\in S} a_j = \sum_{i=1}^{x} A_i $$

于是最大独立集大小可以写成： $$ \text{MIS} = \max_{0 \le x \le n} \left\{ \sum_{i=1}^{n} \max(0, b_i - x) + \sum_{i=1}^{x} A_i \right\} $$

题解里的公式就是这个： $$ \max_{x=0}^n \left\{ \sum_{i=1}^n \max(0, b_i - x) + \sum_{i=1}^x A_i \right\} $$

最后答案（最大匹配）为： $$ \text{Ans} = n^2 - \text{MIS} = n^2 - \max_{0\le x\le n} \left\{ \sum_{i=1}^{n} \max(0, b_i - x) + \sum_{i=1}^{x} A_i \right\} $$

这一步就把“图论 + 结构分析”完整闭环起来了。

七、数据结构那块再解释一下（和代码对应）

题解里后面的“数据结构优化”+ 代码，其核心就是如何维护上面的函数： $$ F(x) = \sum_{i=1}^{n} \max(0, b_i - x) + \sum_{i=1}^{x} A_i $$

并支持单点修改 $a$ / $b$ 后快速更新所有 $x$ 的 $F(x)$ 值的最大值。

1. 静态建初值（对应代码里的 build 部分）

首先用「二维差分 + 一维线段树扫描」做所有矩形翻转，得到初始颜色。
在这个基础上：
- $a$：每一“列”的白格子数（代码里行列交换了）；
- $b$：每一“行”的黑格子数。
把 $a$ 排序得到 $A$，构造与 $A$ 有关的那一段 $\sum_{i=1}^x A_i$；
利用差分数组 tb 把 $\sum_{i=1}^n \max(0, b_i - x)$ 写成一系列对区间 $[0,n]$ 上的加法，最后得到 tt 线段树叶子上存的就是 $F(x)$ 的值；
取 tt.qrymx() 就得到 $\max_x F(x)$。

上面这些，在前面我们已经从数学上验证过 tb + 区间加的正确性，这里就不重复展开。

2. 修改一个格子时的更新（对应后半段代码）

每次单点翻转 $(r,c)$ 的颜色，会导致：

所在行 / 列某一维度的“白格子数” +1 或 -1；
所在列 / 行另一维度的“黑格子数” +1 或 -1。

在公式里，就是某个 $a_r$ 变为 $a_r \pm 1$，某个 $b_c$ 变为 $b_c \pm 1$。

而：

改 $a_r$：影响排序后的 $A$ 数组中某个元素所在位置的值，再通过线段树对 一段前缀 / 后缀做区间加减（因为 $\sum_{i=1}^{x} A_i$ 对所有 $x$ 有规律的影响）；代码里用 al[]、ar[] 来维护某个“值大小段”在排序后的位置区间。
改 $b_c$：直接在 $F(x)$ 中对所有 $x \le b_c$ 或 $x \le b_c-1$ 做线性变化，也可以被翻译成区间加，于是同样用线段树实现。

这就是代码中 tt.add(区间, v) 的逻辑来源：本质就是把对 $a,b$ 的单点变化，转化成对所有 $x$ 上 $F(x)$ 的一段“斜率+截距”变化。

每次改完后，再取一次 tt.qrymx() 就是新的 $\max_x F(x)$，再用 $n^2 - \text{这个值}$ 输出答案。

到这里，题解里的几个“跳得比较快”的点：

最大匹配 → 最大独立集；
最大独立集的“行列同色”结构；
用 $S,T$ 来描述独立集；
一行从白改黑的增量是 $b_i - |S|$ 且与 $S$ 的具体内容无关；
排序列得到 $\max_x {\sum \max(0,b_i-x) + \sum_{i\le x} A_i}$；

都已经补上完整的证明和推导了。

1108T4题解