需开O2优化

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;

const int N = 1e6 + 10;
int n, m, ans;
int f[N], p[N], q[N];

int find(int x) {
    int z = x;
    while (z != f[z]) z = f[z];
    while (x != z) {
        int next = f[x];
        f[x] = z;
        x = next;
    }
    return z;
}

void merge(int a, int b) {
    if (!a || !b) return;
    int fa = find(a);
    int fb = find(b);
    if (fa != fb) {
        p[fa] = max(p[fa], p[fb]);
        f[fb] = fa;
    }
}

void solve(int b[], int l, int r) {
    if (l == r) return;
    int x = (l + r) >> 1;
    solve(b, l, x);
    solve(b, x + 1, r);

    int mn = 0x3f3f3f3f, mx = -0x3f3f3f3f;
    for (int i = l; i <= r; i ++ ) {
        if (i <= x) mx = max(mx, q[b[i]]);
        else mn = min(mn, q[b[i]]);
    }

    int last = 0;
    for (int i = l; i <= r; i ++ ) {
        if (i <= x) {
            if (mn < q[b[i]]) {
                merge(last, b[i]);
                last = b[i];
            }
        } else {
            if (q[b[i]] < mx) {
                merge(last, b[i]);
                last = b[i];
            }
        }
    }

    int p = x + 1, t = l;
    int a[r - l + 1];
    for (int i = l; i <= x;) {
        while (p <= r && q[b[p]] < q[b[i]]) {
            a[t - l] = b[p ++];
            t ++;
        }
        a[t - l] = b[i ++];
        t ++;
    }
    while (p <= r) {
        a[t - l] = b[p ++];
        t ++;
    }
    for (int i = l; i <= r; i ++ ) {
        b[i] = a[i - l];
    }
}

signed main() {

    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            int x;
            cin >> x;
            int u = (i - 1) * m + j;
            f[u] = u;
            q[u] = p[u] = x;
        }
    }

    for (int i = 1; i <= n; i ++ ) {
        int b[m + 1];
        for (int j = 1; j <= m; j ++ ) {
            b[j] = (i - 1) * m + j;
        }
        solve(b, 1, m);
    }

    for (int i = 1; i <= m; i ++ ) {
        int b[n + 1];
        for (int j = 1; j <= n; j ++ ) {
            b[j] = (j - 1) * m + i;
        }
        solve(b, 1, n);
    }

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            ans += p[find((i - 1) * m + j)];
        }
    }

    printf("%.6f", (double)ans / (n * m));

    return 0;
}