给一个 \(n \times m\) 的矩阵和 \(n \times m\) 个数，你需要把这些数填入矩阵。保证
\[\sum_{i=1}^n \sum_{j=1}^m \left ( \mathop{max}\limits_{1 \leq x \leq i, 1 \leq y \leq j} a_{x, y} - \mathop{min}\limits_{1 \leq x \leq i, 1 \leq y \leq j} a_{x, y} \right ) \]在所有填数方案中最大。
输出这个最大值。
显然所求是所有二维前缀的最大值减去最小值之和。
不难想到：
- 若最大值放在 \(a_{1, 1}\) ，则前缀最大值为定值。此时只需要让前缀最小值尽可能小。
- 于是最小值和次小值在 \(a_{1, 2}\) 和 \(a_{2, 1}\) 的位置，就能取遍除 \(s_{1, 1}\) 外的前缀最小值。
- 若最小值放在 \(a_{1, 1}\) ，则前缀最小值为定值。
- 于是最大值和次大值在 \(a_{1, 2}\) 和 \(a_{2, 1}\) 的位置，就能取遍除 \(s_{1, 1}\) 外的前缀最大值。
- 没有其他情况可能产生更大贡献。
不妨让 \(n \geq m\) 。设 \(mx_1, mx_2\) 为最大值和次大值，\(mi_1, mi_2\) 为最小值和次小值。
\(s_{1, 1}\) 不会产生贡献。
假设 \(a_{1, 1}\) 为最大值。则最小值要占据尽可能多的贡献，次小值占据剩下的贡献，以保证最小前缀的和最小。
则 \(min\_s_{1, 2 \sim n - 1}\) 为最小值，\(min\_s_{2 \sim m - 1, 1}\) 为次小值，\(min\_s_{2 \sim n, 2 \sim m}\) 为最小值。
\(ans_1 = (n \times m - 1) mx_1 - m (n - 1) mi_1 - (m - 1) mi_2\) 。
假设 \(a_{1, 1}\) 为最小值。则最大值要占据尽可能多的贡献，次大值占据剩下的贡献，以保证最大前缀的和最大。
则 \(max\_s_{1, 2 \sim n - 1}\) 为最大值，\(min\_s_{2 \sim m - 1, 1}\) 为次大值，\(min\_s_{2 \sim n, 2 \sim m}\) 为最大值。
\(ans_2 = m (n - 1) mx_1 + (m - 1) mx_2 - (n \times m - 1) mi_1\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
int n, m; std::cin >> n >> m;
int mx1 = -1 << 30, mx2 = -1 << 30, mi1 = 1 << 30, mi2 = 1 << 30;
for (int i = 0; i < n * m; i++) {
int x; std::cin >> x;
if (x > mx1) mx2 = mx1, mx1 = x;
else if (x > mx2) mx2 = x;
if (x < mi1) mi2 = mi1, mi1 = x;
else if (x < mi2) mi2 = x;
}
if (n < m) std::swap(n, m);
ll ans1 = 1LL * (n * m - 1) * mx1 - 1LL * m * (n - 1) * mi1 - 1LL * (m - 1) * mi2;
ll ans2 = 1LL * m * (n - 1) * mx1 + 1LL * (m - 1) * mx2 - 1LL * (n * m - 1) * mi1;
std::cout << std::max(ans1, ans2) << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}