Descirption

给定 \(n\times m\) 的矩阵，求出最大子矩阵使得每行每列都是等差数列。

Solution

处理出 \(d_{i,j}=a_{i,j}-a_{i,j-1}\)，将每行分成若干段极长等差数列。但这些等差数列会有 \(1\) 个位置重叠，于是考虑记录 \([l,r]\) 的等差数列为 \((l+1,r)\).

观察发现若干行等差数列在列上也是等差数列仅当它们的首项构成等差数列、公差也构成等差数列。

考虑使用悬线法，处理 \(up_{i,j}\) 为最大的 \(k\) 使得第 \(j\) 列上 \([k-1,i]\) 构成等差数列，\(l_{i,j}\) 为最小的 \(k\) 使得 \(i\) 行上 \([k-1,j]\) 构成等差数列，\(r_{i,j}\) 为最大的 \(k\) 使得 \([j,k]\) 构成等差数列。为了保证合法，再处理 \(L_{i,j}\) 为在保证矩阵上边界为 \(up_{i,j}-1\) 的情况下最小的 \(k\) 使得 \(i\) 行上 \([k-1,j]\) 构成等差数列，\(R_{i,j}\) 为在保证矩阵上边界为 \(up_{i,j}-1\) 的情况下最大的 \(k\) 使得 \([j,k]\) 构成等差数列。

枚举答案的 \(i,j\) 时需要注意需要考虑 \(up_{i,j}-1\)，故左边界为 \(tL=\min\{L_{i,j},l_{up_{i,j}-1,j}\}\)，右边界 \(tR=\max\{R_{i,j},r_{up_{i,j}-1,j}\}\)。答案为 \(\displaystyle\max_{i,j}\{(tR-tL+2)(i-up_{i,j}+2)\}\)。

注意边界，需要特判答案矩阵宽为 \(1\) 的情况。

时间复杂度 \(\mathcal{O}(\sum nm)\)。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Milkcat {
    typedef long long LL;
    const int N = 3005;
	LL n, m, ans, a[N][N], d[N][N], up[N][N], l[N][N], r[N][N], L[N][N], R[N][N];
	int main() {
		cin >> n >> m, ans = 1;
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= m; j ++)
				cin >> a[i][j], d[i][j] = a[i][j] - a[i][j - 1];
		for (int i = 1; i <= n; i ++)
			for (int j = 2; j <= m; j ++) {
				l[i][j] = r[i][j] = j;
				if (i >= 2) up[i][j] = i;
			}
		for (int i = 1; i <= n; i ++) {
			for (int j = 3; j <= m; j ++)
				if (a[i][j] + a[i][j - 2] == a[i][j - 1] * 2) l[i][j] = l[i][j - 1];
			for (int j = m - 1; j > 1; j --)
				if (a[i][j + 1] + a[i][j - 1] == a[i][j] * 2) r[i][j] = r[i][j + 1];
			for (int j = 2; j <= m; j ++)
				L[i][j] = l[i][j], R[i][j] = r[i][j];
		}
		for (int i = 3; i <= n; i ++)
			for (int j = 2; j <= m; j ++) {
				if (a[i][j] + a[i - 2][j] == a[i - 1][j] * 2 && d[i][j] + d[i - 2][j] == d[i - 1][j] * 2) {
					up[i][j] = up[i - 1][j];
					L[i][j] = max(L[i][j], L[i - 1][j]);
					R[i][j] = min(R[i][j], R[i - 1][j]);
				}
			}
		for (int i = 2; i <= n; i ++)
			for (int j = 2; j <= m; j ++) {
				int tR = min(R[i][j], r[up[i][j] - 1][j]);
				int tL = max(L[i][j], l[up[i][j] - 1][j]);
				ans = max(ans, (tR - tL + 2) * (i - up[i][j] + 2)); 
			}
		for (int i = 1; i <= n; i ++) {
			if (m < 2) break;
			LL s = 2; ans = max(ans, s);
			for (int j = 3; j <= m; j ++)
				s = d[i][j] == d[i][j - 1] ? s + 1 : 2, ans = max(ans, s);
		}
		for (int i = 1; i <= m; i ++) {
			if (n < 2) break;
			LL s = 2; ans = max(ans, s);
			for (int j = 3; j <= n; j ++)
				s = a[j][i] + a[j - 2][i] == a[j - 1][i] * 2 ? s + 1 : 2, ans = max(ans, s);
		}
		cout << ans << '\n';
		return 0;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    int T = 1; cin >> T;
    while (T --) Milkcat::main();
    return 0;
}