T5
题目大意
有 nnn 个水平线段和 mmm 个垂直线段，每个线都有一个颜色，开始横竖导线之间是绝缘的，你可以执行如下的操作，让一次横着的导线和竖着的导线之间导电，问最少经过多少次操作，相同颜色的线缆之间会导电。问最少经过多少次操作，会让所有的的颜色想相同的导线之间导电，在最少的操作次数下，有多少种可能的操作方法。
题解思路
问题一：单色焊接
问题描述：
有 nnn 个水平线段和 mmm 个垂直线段，所有线段颜色相同。需要多少次焊接才能将所有线段连接成一个整体？有多少种不同的焊接方案？
分析：
1. 焊接次数：
* 每次焊接可以连接一个水平线段和一个垂直线段。初始时有 nnn 个水平线段和 mmm 个垂直线段，最终需要连接成一个整体（即 1 个连通块）。
* 每次焊接减少 1 个独立线段（因为焊接是将两个线段连接，相当于减少 1 个独立单位）。
* 初始独立线段数为 n+mn + mn+m，最终为 1，因此需要 (n+m)−1=n+m−1(n + m) - 1 = n + m - 1(n+m)−1=n+m−1 次焊接。
2. 焊接方案数：
* 焊接顺序可以建模为一个路径问题：从 (0,0)(0, 0)(0,0) 到 (n,m)(n, m)(n,m)，每次选择焊接一个水平线段（向右走）或一个垂直线段（向上走）。
* 总步数为 n+mn + mn+m，其中 nnn 步向右，mmm 步向上。
* 因此方案数为组合数 (n+mn)\binom{n + m}{n}(nn+m )。
* 但焊接是从第一个焊接开始的，所以实际路径是从 (1,1)(1, 1)(1,1) 到 (n,m)(n, m)(n,m)，步数为 (n−1)+(m−1)=n+m−2(n - 1) + (m - 1) = n + m - 2(n−1)+(m−1)=n+m−2，方向为 n−1n - 1n−1 右和 m−1m - 1m−1 上。
* 因此方案数为 (n+m−2n−1)\binom{n + m - 2}{n - 1}(n−1n+m−2 )。
结论：
* 焊接次数：n+m−1n + m - 1n+m−1 次。
* 方案数：(n+m−2n−1)\binom{n + m - 2}{n - 1}(n−1n+m−2 )。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
问题二：双色焊接
问题描述：
现在有两种颜色的线段（颜色 aaa 和 bbb）：
* 颜色 aaa 的覆盖范围为左上角 (x1,y1)(x_1, y_1)(x1 ,y1 ) 到右下角 (x2,y2)(x_2, y_2)(x2 ,y2 )。
* 颜色 bbb 的覆盖范围为左上角 (x3,y3)(x_3, y_3)(x3 ,y3 ) 到右下角 (x4,y4)(x_4, y_4)(x4 ,y4 )。
需要将两种颜色的线段分别连通。问如何焊接？如果两种颜色的范围有重叠，如何处理？
分析：
1. 无重叠情况：
* 如果颜色 aaa 和 bbb 的矩形区域不重叠（即 x2<x3x_2 < x_3x2 <x3 或 x4<x1x_4 < x_1x4 <x1 或 y2<y3y_2 < y_3y2 <y3 或 y4<y1y_4 < y_1y4 <y1 ），则可以完全独立处理。
* 分别对颜色 aaa 和 bbb 使用问题一的思路。
2. 有重叠情况：
* 如果颜色 aaa 和 bbb 的矩形区域重叠，那么他们的焊接路径一定会有冲突。那么我们可以将两个颜色当成一个颜色，这样就可以多通过一次操作避免冲突。
因此本题就是看不同颜色的区间范围是否存在冲突，存在冲突的点则当成一个颜色来连接。
复杂度分析
O（max(n,m)\max(n,m)max(n,m)）
参考代码
