題目鏈接：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)$ 的邊。

為了方便，做幾點說明。

• 逆序對連邊生成的邊集為 $E_0$，相鄰連邊生成的邊集為 $E_1$；
• 簡寫 $(l,j)$ 到 $(r,j)$ 連雙向邊為 $l?r$。

下面證明二者等價。

若有 $a_{l,j}>a_{r,j}$，那么有 $l?r$，那么對于 $i\in [l,r)$，一定有 $pre[i]>suf[i+1]$，那也就是說，$E_1$ 會包含 $l?l+1,l+1?l+2,?,r?1?r$，這相當于包含了一條 $l?r$ 的雙向邊，所以 $E_0?E_1$。

若有 $pre[i]>suf[i+1]$，那么有 $i?i+1$，同時，由前綴最大和后綴最小的性質可以得到，必然存在 $l\in [1,i]$ 和 $r\in (i,n]$，使得 $a_{l,j}>a_{r,j}$，那么首先就有 $l?r$。如果 $l<i$，說明 $a_{l,j}>a_{i,j}$，那么由題目條件有 $l?i$，同理如果 $i+1<r$，那么 $i+1?r$，將這三條邊合起來，就包含了一條 $i?i+1$ 的雙向邊，所以 $E_1?E_0$。

綜上，$E_0=E_1$，二者等價。

設我們這樣得到了 $N$ 個連通塊，第 $i$ 個連通塊的大小為 $si{z}_i$，其塊內最大值為 ${\max }_i$，則最終答案為

$$\sum _{i=1}^{N}si{z}_i\times ma{x}_i.$$

時間復雜度 $O(\mathrm{nm}?\alpha (\mathrm{nm}))$

• 其中 $\alpha (\mathrm{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;
}