【SP21463 题解】

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