Descirption
- 给定 \(n\times m\) 的矩阵，求最大子矩阵的面积满足每一行每一列都构成等差数列。
Solution
我们另 \(up_{i, j}\) 表示最小的 \(k\) 满足 \((i, k), (i, k+1),\cdots, (i, j)\) 构成等差数列，可以用 \(\mathcal O(nm)\) 求出。
对于一个矩阵的左上角 \((a, b)\)，右下角 \((c, d)\)，\(b\sim d\) 中每一列都构成等差数列，则只需满足 \(a\sim c\) 中需要两行构成等差数列，则所有行都构成等差数列。
根据 玉蟾宫 相似的思路，做一遍单调栈。
枚举 \(i\) 表示第几行为底的，然后每个直立方图的高度为 \(up_{i, j}\)，根据上面所述的性质判断 \(i\) 和 \(i-1\) 行是否为等差数列即可。
时间复杂度：\(\mathcal O(nm)\)。
参考代码：
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> a(n + 1, std::vector<int>(m + 1));
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
std::cin >> a[i][j];
}
}
std::vector<std::vector<int>> up(n + 1, std::vector<int>(m + 1));
for (int j = 1; j <= m; j ++ ) {
up[1][j] = 1;
for (int i = 2; i <= n; i ++ ) {
if (i == 2 || a[i][j] - a[i - 1][j] == a[i - 1][j] - a[i - 2][j]) {
up[i][j] = up[i - 1][j];
} else {
up[i][j] = i - 1;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i ++ ) {
int lst = 1;
for (int j = 2; j <= m; j ++ ) {
if (j != 2 && a[i][j] - a[i][j - 1] != a[i][j - 1] - a[i][j - 2]) {
lst = j - 1;
}
ans = std::max(ans, j - lst + 1);
}
lst = 1;
for (int j = 1; j <= m; j ++ ) {
if (j == m || (j > 1 && (a[i][j + 1] - a[i][j] != a[i][j] - a[i][j - 1] || a[i - 1][j + 1] - a[i - 1][j] != a[i - 1][j] - a[i - 1][j - 1]))) {
std::vector<int> stk;
std::vector<int> l(m + 1), r(m + 1);
for (int k = lst; k <= j; k ++ ) {
while (stk.size() && up[i][k] >= up[i][stk.back()]) {
stk.pop_back();
}
l[k] = stk.size() ? stk.back() + 1 : lst;
stk.push_back(k);
}
std::vector<int>().swap(stk);
for (int k = j; k >= lst; k -- ) {
while (stk.size() && up[i][k] >= up[i][stk.back()]) {
stk.pop_back();
}
r[k] = stk.size() ? stk.back() - 1 : j;
stk.push_back(k);
}
for (int k = lst; k <= j; k ++ ) {
ans = std::max(ans, (i - up[i][k] + 1) * (r[k] - l[k] + 1));
}
lst = j;
}
}
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int t;
std::cin >> t;
while (t -- ) {
solve();
}
return 0;
}