题解：P12169 [蓝桥杯 2025 省 C/Python A/Java C] 登山

· · 题解

算法：并查集

由于行列是同一套逻辑，所以下面只说同一列内的行操作，同一行内的列操作直接照抄即可。

设现在我们在 (x, y)，且存在点 (i, y) 满足 i > x 且 a_{i, y} < a_{x, y}，那么我们可以从 (x, y) 向 (i, y) 连边表示 (x, y) 可达 (i, y)。

那么同理，如果我们在 (i, y)，根据题中所说，(x, y) 满足 x < i 且 a_{x, y} > a_{i, y}，同样可以从 (i, y) 向 (x, y) 连边。

也就是说，只要存在一个逆序对，就有一对双向边！

但是直接 O(n^2) 遍历 O(m) 次复杂度过高，所以我们需要逆序对连边的等价命题。

先给出命题：对于第 j 列，设 pre[i] 表示前 i 个元素的最大值，suf[i] 表示 [i, n] 内元素的最小值，如果 pre[i] > suf[i + 1]，就连一条 (i, j) 到 (i + 1, j) 的边。

为了方便，做几点说明。

下面证明二者等价。

若有 a_{l, j} > a_{r, j}，那么有 l \Longleftrightarrow r，而对于 i \in [l, r)，一定有 pre[i] > suf[i + 1]，那也就是说，E_1 会包含 l \Longleftrightarrow l + 1, \ \ l + 1 \Longleftrightarrow l + 2, \ \ \cdots, \ \ r - 1 \Longleftrightarrow r，这相当于包含了一条 l \Longleftrightarrow r 的双向边，所以 E_0 \subseteq E_1。

若有 pre[i] > suf[i + 1]，那么有 i \Longleftrightarrow i + 1，同时，由前缀最大和后缀最小的性质可以得到，必然存在 l \in [1, i] 和 r \in (i, n]，使得 a_{l, j} > a_{r, j}，那么首先就有 l \Longleftrightarrow r。如果 l < i，说明 a_{l, j} > a_{i, j}，由题目条件有 l \Longleftrightarrow i，同理如果 i + 1 < r，那么 i + 1 \Longleftrightarrow r，将这三条边合起来，就包含了一条 i \Longleftrightarrow i + 1 的双向边，所以 E_1 \subseteq E_0。

综上，E_0 = E_1，二者等价。

设我们这样得到了 N 个连通块，第 i 个连通块的大小为 siz_i，其块内最大值为 \max_i，则最终答案为

\sum\limits_{i = 1}^{N}siz_i \times max_i.

时间复杂度 O(\rm{nm \cdot \alpha(nm)})

C++ Code

#include <bits/stdc++.h>

using i64 = long long;

struct DSU {
    std::vector<int> f, sz;
    DSU() {}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        sz.assign(n, 1);
    }
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    int size(int x) {
        return sz[find(x)];
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        sz[x] += sz[y];
        f[y] = x;
        return true;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

template<class T>
void chmax(T &a, T b) {
    if (a < b) {
        a = b;
    }
}
constexpr int inf = std::numeric_limits<int>::max() / 2;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cout << std::fixed << std::setprecision(6);

    int n, m;
    std::cin >> n >> m;

    const int N = n * m;

    std::vector<int> a(N);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> a[i * m + j];
        }
    }

    DSU dsu(N);
    for (int i = 0; i < n; i++) {
        std::vector pre(m + 1, 0);
        std::vector suf(m + 1, inf);
        for (int j = 0; j < m; j++) {
            pre[j + 1] = std::max(pre[j], a[i * m + j]);
        }
        for (int j = m - 1; j >= 0; j--) {
            suf[j] = std::min(suf[j + 1], a[i * m + j]);
        }
        for (int j = 1; j < m; j++) {
            if (pre[j] > suf[j]) {
                dsu.merge(i * m + (j - 1), i * m + j);
            }
        }
    }
    for (int j = 0; j < m; j++) {
        std::vector pre(n + 1, 0);
        std::vector suf(n + 1, inf);
        for (int i = 0; i < n; i++) {
            pre[i + 1] = std::max(pre[i], a[i * m + j]);
        }
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = std::min(suf[i + 1], a[i * m + j]);
        }
        for (int i = 1; i < n; i++) {
            if (pre[i] > suf[i]) {
                dsu.merge((i - 1) * m + j, i * m + j);
            }
        }
    }

    std::vector max(N, 0);
    for (int i = 0; i < N; i++) {
        chmax(max[dsu.find(i)], a[i]);
    }
    i64 ans = 0;
    for (int i = 0; i < N; i++) {
        if (dsu.find(i) == i) {
            ans += 1LL * dsu.size(i) * max[i];
        }
    }
    std::cout << 1.* ans / n / m << "\n";

    return 0;
}