自动搬运

查看原文

来自洛谷，原作者为

	Levisuper **

搬运于2025-08-24 23:13:21，当前版本为作者最后更新于2025-04-22 00:12:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

算法：并查集

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

设现在我们在 $(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)$ 的边。

为了方便，做几点说明。

• 逆序对连边生成的边集为 $E_0$，相邻连边生成的边集为 $E_1$；
• 简写 $(l, j)$ 到 $(r, j)$ 连双向边为 $l \Longleftrightarrow r$。

下面证明二者等价。

若有 $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$，则最终答案为

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

• 其中 $\rm{\alpha(nm)}$ 是反阿克曼函数，一般可以看作 $3, 4$ 左右的常数。

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;
}