CF1368H 题解

· · 题解

一种不一样的方法。

题意

有一个 n\times m 的网格，相邻格点之间有边。在最外围每个位置有一个红色或蓝色的发射器，要求将一些发射器配对，满足一个是红色，一个是蓝色，且存在一种从所有选择的红色发射器连到选择的蓝色发射器的路径，满足每条边被经过至多一次。需要支持 q 次区间颜色翻转的修改。n,m,q\le10^5。

思路

先考虑无修改的版本怎么做。这显然是一个最大流问题，但最大流并没有什么很好的性质，于是我们转成最小割处理。最小割还是不太好做，于是再将最小割转成对偶图，若源汇唯一，那么最小割就等于两个无界面之间的最短路。这题中源汇不唯一，因此考虑类似 CSP-2021 交通规划 的处理方式，将相邻两个不同色的点之间的区域拿出来，先进行一次两两匹配之后计算每组匹配的最短路之和，在所有匹配中的最小值即是答案。

做好转化之后，考虑怎么样快速解决这个问题。由于所有边边权为 1，所以两点之间最短路就是它们的曼哈顿距离。因此可以将问题重新叙述为，给定矩形四周上的若干个点，将它们两两匹配，最小化每组匹配的曼哈顿距离之和。经过一些观察，可以发现对于矩形的相邻两条边上的点，例如左侧和上侧，它们之间的匹配最多只可能有一对，且如果有，一定是上侧边的最左侧点和左侧边的最上侧点进行匹配。否则可以调整使得答案更优。则可以首先 2^4 枚举拐角处是否匹配了，将这些贡献扣掉之后就只需要考虑两对相对的边的贡献，以上下两边为例。

考虑上侧哪些点和下侧的点进行了匹配，假设确定了这个集合为 S。则对于每个 S 中的点，先以 n 的代价将它移到下面，然后就变成了上下两边独立的问题。在一维线段上，这个问题是容易的，直接相邻两个点匹配即可，于是只需要能够确定 S 中的点，就可以算出贡献。这样可以想到一个 dp，记 f_{i,j,k} 表示考虑了 0\sim i 这些列，上面最后一个未匹配的点是 j，下面是 k 的答案。但这样状态太多了，于是需要优化。进一步观察可以发现，若上面某一个点被和下面的一个点匹配了，那么这个时候上面和下面一定都没有在它们前面的未匹配点。否则假设上面有，那么交换这两个点最终匹配的点一定不会使答案更劣。这样状态中的 j,k 若存在，则一定是 i 前面的最后一个点，于是只需要记 f_{i,0/1,0/1} 表示上下两边是否有未匹配的点即可。这样转移有两种，如果单加一个点，那么翻转其对应位的状态，且如果匹配了增加对应的贡献。若增加一个点的同时和另一侧的未匹配点进行了匹配，则只能是上面原先没有未匹配的点。这样可以 O(1) 转移，复杂度 O(2^4n)。

下面考虑支持修改操作。由于我们只关心相邻不同的字符，所以区间翻转操作对于这些位置就是单点加与删除的操作。那么一次操作对于前面这个做法的影响主要在于求 dp 的过程，对于枚举拐角的部分，使用 set 维护所有剩余位置即可以直接查找。但这个 dp 式子里涉及形如 <i 的最大元素一类的东西，所以对转移的修改并不是完全的单点修改。不过我们可以修改一下这个 dp，对于 f_{i,1,*} 这些状态，我们定义其现在的值为其真实含义对应的值减去 i 前面的最后一个上侧点位置的值。思考一下这是什么含义，由于 f_{i,1,*}\to f_{j,0,*} 的时候，贡献是 j-i，所以我们将贡献拆开，在 f_{i,1,*} 处减去 i，在 f_{j,0,*} 处加 j。分析一下所有情况发现这么修改定义之后，可以对应地修改转移方式，使得所有转移都只和当前位置有关。由于转移是矩阵的形式，所以做一次动态 dp，线段树维护即可做到 O(2^44^3n\log n) 的复杂度，应该无法通过。

接下来应该怎么优化呢？发现这个 2^4 乘在上面太浪费了，因为不同的拐角处的选择方式只影响最开始和末尾的一个位置，对整个 dp 的过程本质上没有什么影响。所以考虑能否在外面算出来一些东西再枚举拐角算贡献。由于已经天然地写成了矩阵的形式，所以可以充分利用这个矩阵。记答案矩阵的 (i,j) 这个位置表示初始状态为 i，终止状态为 j 的答案。这里的初始状态是什么意思呢？考虑先扣除两侧点的最前面的一个，若在最终状态里选择了某个最前面的点，那么初始状态中这一位是 1，表示这个点是未匹配的，否则是 0，表示已经匹配。终止状态也是类似的定义。这样确定了拐角选择方式之后可以唯一确定初始和终止状态，因此直接在答案矩阵中查找即可。复杂度变为 O((2^4+4^3)n\log n)，常数不大，可以通过。

但这样有一个细节上的问题。例如若上侧的最前面的点是空余的，则它可以进行匹配，这个匹配点也可以是下面中间的某个点。但在刚刚这个过程中，我们 dp 贡献方式是先进入 dp 数组的点贡献 -1，后进入的贡献 1，这样如果最终上面的点和下面前面的一个点匹配了，会带来负的贡献，这是不符合题意的。解决方案也不困难，显然只有下面最靠近上面最前面的点的这个点可能与它进行匹配，所以对于所有这个位置之前的部分，将这种转移去掉重新计算转移矩阵，对于这个特别的可以与它匹配的点，因为只有一个，暴力使用绝对值转移即可。由于后面的部分转移的贡献是正常的，所以不需要做改变。这样线段树中维护两个矩阵的乘积即可。

代码只有 10K，并不是很长。

代码