CF1368H
给定一张 (n imes m) 网格，每行/每列的边界处均有一个端口，端口有红色也有蓝色。
你需要在这些网络中连接一些线缆，满足：
- 线缆必须连接一个红色端口和蓝色端口，每个端口至多作为一条线缆的端点。
- 线缆的每一段必须是水平/竖直的，只能在交点处转弯。
- 任何两条线段不能有长度大于 (0) 的相交部分，即只能在端点处相交。
定义网络的容量为，在此限制下，至多可以连接的线缆数。
进行 (q) 次修改，每次修改为将一段区间的端口颜色取反。
对于每次修改，计算答案。
- (mathbf{for~H1})，(n,mle 10^5,q=0)
- (mathbf{for~H2})，(n,m,qle 10^5)
Solution
- (mathbf{H1})
先考虑 (mathbf{H1})，即没有修改如何处理。
发现每个线段只能被经过一次，考虑网络流建模
(S) 连向红色端口，蓝色端口连 (T)，每两个节点连一条容量为 (1) 的双向边，即反向边和正向边容量均为 (1)（或者说连接无向边）
我们可以认为这张图是无向图，于是不妨从最小割的角度考虑此题。
等价于找到最小的边集，使得红色点和蓝色点不联通。
我们发现这张图有类似于网格图般的形式，此时我们发现其最小割等价于将每个点赋一个颜色，如果相邻两个点颜色不同答案 (+1)
同时，我们发现答案的上界是 (min( m{黑色点}， m{红色点})) 的数量，换而言之，答案一定小于等于 (n+m)
假设 (m>n) 即每行的长度大于每一列，我们考虑每一列的贡献。
我们发现假设每一列的颜色均存在一个分界点使得颜色不同，那么此时答案的下界是 (m)（即所有颜色均对齐）
我们发现假设每一列均存在两个分界点，那么答案的下界将到达 (2m>n+m)
于是我们不可能使得所有列均存在至少两个分界点。
假设部分列均只有一个分界点，某个列存在两个分界点，那么考虑将其调整为只有一个分界点的情况，不难发现一定不会变劣。
于是每个列只有一个分界点。
仍然考虑 (m>n)
假设 (m>nge 2)，我们发现假设某个列为颜色相同，且相邻的列均为只有一个分界点。
我们发现此时答案将所有列调整为均为同色状态或者将所有列调整为只有一个分界点，两者肯定有一个比现状优。
这是因为只有一个分界点的列至少会产生 (1) 的贡献。可以类似于将颜色集体推下去，这样可以减少边界上颜色产生的贡献（注意到边界至少有 (2) 的贡献，这样等价于行的贡献的最大值）
或者将颜色均调整过来，来减少列的贡献。
于是我们发现答案只有两种情况：
- 所有列均同色。
- 所有列均只有一个分界点。
考虑情况 (2)，我们发现我们必然会使得所有列的分界点位于相同的位置。（或者说行形如：全 A，全 A ... 全 A，全 B，全 B ... 全 B 这种形式）
因为如果不相同此时这一行至少有 (1) 的贡献，那么可以选择两种方式调整为相同（要么另一边缩进来，要么另一边出去）这样至少可以达到低于不相同的贡献。（因为两种选择的贡献和为总量，那么必然有一者小于总量除以 (2)（即原贡献））
然后我们发现 (n=1) 的时候必然会满足所有列相同。
所以最后答案的情况仅有两种：
- 所有列颜色相同。
- 所有列均只有一个分界点。
然而这样需要根据 (m) 和 (n) 的大小关系进行分类讨论，太麻烦了，所以我们考虑弱化限制 (2) 变成所有行颜色相同的情况下的答案。
不难发现其包括了原命题，且我们得到了一个对于任意 (m,n) 均适用的限制：
- 所有列颜色相同。
- 所有行颜色相同。
最终答案为这两种答案取 (min) 的结果。
于是可以使用 dp 来统计贡献。复杂度 (mathcal O(n+m))
- (mathbf{H2})
考虑 H1 的 dp 式：
(f_{i,0}=min(f_{i-1,0},f_{i-1,1}+n)+w(i,0))
(f_{i,1}=min(f_{i-1,0}+n,f_{i-1,1})+w(i,1))
- 另一面的处理类似。
考虑使用 ddp 来维护其，这样我们的矩阵转移应该形如：
考虑怎么支持翻转一段区间。
我们发现可以维护一个翻转标记，同时提前维护底层的点的状态和翻转后的状态。注意需要维护 (4) 种状态。
这样使用 ddp 维护矩阵乘法即可。
复杂度 (mathcal O(q(log n+log m)))
代码又枯了，有空会回来补的，最近被代码搞烦了，不太想写。
(Code~mathbf{for~H1})
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int N = 1e5 + 5 ;
int n, m, Ans, q, ll, rr, dd, uu, L[N], R[N], D[N], U[N], dp[N][2] ;
char s[N] ;
signed main()
{
n = gi(), m = gi(), q = gi() ; Ans = n + m ;
scanf("%s", s + 1 ) ;
rep( i, 1, n ) if(s[i] == 'R') L[i] = 1, ++ ll ;
scanf("%s", s + 1 ) ;
rep( i, 1, n ) if(s[i] == 'R') R[i] = 1, ++ rr ;
scanf("%s", s + 1 ) ;
rep( i, 1, m ) if(s[i] == 'R') U[i] = 1, ++ uu ;
scanf("%s", s + 1 ) ;
rep( i, 1, m ) if(s[i] == 'R') D[i] = 1, ++ dd ;
dp[0][1] = n - ll,
dp[0][0] = ll ;
rep( i, 1, m ) {
dp[i][0] = min(dp[i - 1][1] + n, dp[i - 1][0]) + U[i] + D[i] ;
dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + n) + (U[i] ^ 1) + (D[i] ^ 1) ;
}
dp[m][0] += rr, Ans = min( Ans, dp[m][0] ) ;
dp[m][1] += (n - rr), Ans = min( Ans, dp[m][1] ) ;
memset( dp, 0, sizeof(dp) ) ;
dp[0][1] = m - uu ;
dp[0][0] = uu ;
rep( i, 1, n ) {
dp[i][0] = min(dp[i - 1][1] + m, dp[i - 1][0]) + L[i] + R[i] ;
dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + m) + (L[i] ^ 1) + (R[i] ^ 1) ;
}
dp[n][0] += dd, Ans = min( Ans, dp[n][0] ) ;
dp[n][1] += (m - dd), Ans = min( Ans, dp[n][1] ) ;
cout << Ans << endl ;
return 0 ;
}