T5

题目大意

有 $n$ 个水平线段和 $m$ 个垂直线段，每个线都有一个颜色，开始横竖导线之间是绝缘的，你可以执行如下的操作，让一次横着的导线和竖着的导线之间导电，问最少经过多少次操作，相同颜色的线缆之间会导电。问最少经过多少次操作，会让所有的的颜色想相同的导线之间导电，在最少的操作次数下，有多少种可能的操作方法。

题解思路

问题一：单色焊接

问题描述：
有 $n$ 个水平线段和 $m$ 个垂直线段，所有线段颜色相同。需要多少次焊接才能将所有线段连接成一个整体？有多少种不同的焊接方案？

分析：

1. 焊接次数：

• 每次焊接可以连接一个水平线段和一个垂直线段。初始时有 $n$ 个水平线段和 $m$ 个垂直线段，最终需要连接成一个整体（即 1 个连通块）。
• 每次焊接减少 1 个独立线段（因为焊接是将两个线段连接，相当于减少 1 个独立单位）。
• 初始独立线段数为 $n + m$，最终为 1，因此需要 $(n + m) - 1 = n + m - 1$ 次焊接。

2. 焊接方案数：

• 焊接顺序可以建模为一个路径问题：从 $(0, 0)$ 到 $(n, m)$，每次选择焊接一个水平线段（向右走）或一个垂直线段（向上走）。
• 总步数为 $n + m$，其中 $n$ 步向右，$m$ 步向上。
• 因此方案数为组合数 $\binom{n + m}{n}$。
• 但焊接是从第一个焊接开始的，所以实际路径是从 $(1, 1)$ 到 $(n, m)$，步数为 $(n - 1) + (m - 1) = n + m - 2$，方向为 $n - 1$ 右和 $m - 1$ 上。
• 因此方案数为 $\binom{n + m - 2}{n - 1}$。

结论：

• 焊接次数：$n + m - 1$ 次。
• 方案数：$\binom{n + m - 2}{n - 1}$。

---

问题二：双色焊接

问题描述：
现在有两种颜色的线段（颜色 $a$ 和 $b$）：

• 颜色 $a$ 的覆盖范围为左上角 $(x_1, y_1)$ 到右下角 $(x_2, y_2)$。
• 颜色 $b$ 的覆盖范围为左上角 $(x_3, y_3)$ 到右下角 $(x_4, y_4)$。
  需要将两种颜色的线段分别连通。问如何焊接？如果两种颜色的范围有重叠，如何处理？

分析：

1. 无重叠情况：

• 如果颜色 $a$ 和 $b$ 的矩形区域不重叠（即 $x_2 < x_3$ 或 $x_4 < x_1$ 或 $y_2 < y_3$ 或 $y_4 < y_1$），则可以完全独立处理。
• 分别对颜色 $a$ 和 $b$ 使用问题一的思路。

2. 有重叠情况：

• 如果颜色 $a$ 和 $b$ 的矩形区域重叠，那么他们的焊接路径一定会有冲突。那么我们可以将两个颜色当成一个颜色，这样就可以多通过一次操作避免冲突。

因此本题就是看不同颜色的区间范围是否存在冲突，存在冲突的点则当成一个颜色来连接。

复杂度分析

O（$\max(n,m)$）

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
#ifndef ONLINE_JUDGE
#include "test.h"
#else

#define debug(...) 42
#define debug_assert(...) 42
#endif

namespace myMath {
    i64 mod = 998244353;

    i64 add(i64 x, i64 y) {
        x += y;
        if (x > mod) x -= mod;
        return x;
    }

    i64 sub(i64 x, i64 y) {
        x -= y;
        if (x < 0)x += mod;
        return x;
    }

    i64 mul(i64 x, i64 y) {
        x *= y;
        x -= x / mod * mod;
        return x;
    }

    i64 qpow(i64 x, i64 y) {
        i64 res = 1;
        while (y) {
            if (y & 1) res = mul(res, x);
            y >>= 1;
            x = mul(x, x);
        }
        return res;
    }

    i64 inv(i64 x) {
        return qpow(x, mod - 2);
    }

    i64 qdiv(i64 x, i64 y) {
        return mul(x, inv(y));
    }

    void set_mod(i64 x) {
        mod = x;
    }

    namespace Comb {
        int n;
        vector<i64> fa;
        vector<i64> ifa;

        void init(int _n) {
            n = _n;
            fa.assign(n + 1, 1), ifa.assign(n + 1, 1);
            for (int i = 1; i <= n; i++) fa[i] = mul(fa[i - 1], i);
            ifa[n] = inv(fa[n]);
            for (i64 i = n - 1; i; i--) {
                ifa[i] = mul(ifa[i + 1], i + 1);
            }
        }

        i64 C(int i, int j) {
            return mul(fa[i], mul(ifa[j], ifa[i - j]));
        }
    }

    //线性求逆元

    vector<i64> get_inv(int k) {
        vector<i64> in(k + 1, 1);
        for (int i = 2; i <= k; i++) {
            in[i] = mul(in[mod % i], sub(mod, mod / i));
        }
        return in;
    }
}

using namespace myMath;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    Comb::init(4e6);
    cin >> n >> m;
    vector<int> cx(n + 1), cy(m + 1);
    vector<int> fx(1e6 + 1, 1e9), tx(1e6 + 1, 1e9), fy(1e6 + 1), ty(1e6 + 1);
    for (int i = 1; i <= n; i++) {
        cin >> cx[i];
        fx[cx[i]] = min(i, fx[cx[i]]);
        tx[cx[i]] = i;
    }
    for (int i = 1; i <= m; i++) {
        cin >> cy[i];
        fy[cy[i]] = min(fy[cy[i]], i);
        ty[cy[i]] = i;
    }
    auto run = [&]() -> pair<i64, i64> {
        int i = 1, j = 1;
        i64 t = 0, sums = 1;
        while (i <= n && j <= m) {
            int fxx = i, txx = max(tx[cx[i]], tx[cy[j]]);
            int fyy = j, tyy = max(ty[cx[i]], ty[cy[j]]);
            int a = 0, b = 0;
            while (i < txx || j < tyy) {
                while (i < txx) {
                    a++;
                    i++;
                    txx = max(tx[cx[i]], txx);
                    tyy = max(ty[cx[i]], tyy);
                }
                while (j < tyy) {
                    b++;
                    j++;
                    txx = max(txx, tx[cy[j]]);
                    tyy = max(tyy, ty[cy[j]]);
                }
            }
            t += a + b + 1;
            sums = mul(sums, Comb::C(a + b, a));
            i++, j++;
        }
        return {t, sums};
    };
    auto [a , b] = run();

    cout << a << "\n" << b << endl;
}