[ARC081F] Flip and Rectangles

考虑转换题目给出的条件。
可以观察到一些性质

• 若某个矩形能被操作为全 \(1\) ，那么其任意子矩形也一定可以。
• 任意行列交换不影响矩阵是否能变为全 \(1\)
  然后重要的来了 任选位置 \([x,y]\) 强制使 \(A[x,y]\) 变为 \(1\)， 不是则取反整个矩阵。然后查看第 \(x\) 行第 \(y\) 列，若有一个数为 \(0\) 则翻转对应列/行。之后再做任何操作都会破坏原本第 \(x\)
  行第 \(y\) 列的 \(1\)。

这等价于，对于位置 \(A[i,j]\) \((i \not= x, j \not= y)\)，检查 \(!A[x,y], !A[i,y], !A[x,j], A[i,j]\) 的异或值是否为 \(1\)。

也即对于位置 \(A[i,j]\) \((i \not= x, j \not= y)\)，检查 \(A[x,y], A[i,y], A[x,j], A[i,j]\) 的异或值是否为 \(0\)。

由于 \([x, y]\) 也是任选的， 所以任意一个子矩形内部四角异或和为 \(0\)。 同时这也充要。

在转化充要条件时，判定算法可能是构造性的。此时要尽量多想“有没有其他方法也可以完成构造？”，以得到更多性质。
比方说，在本题中，若直接选择第一行第一列开始构造（而不是任意的 \([x,y]\)）就很难得到这个性质。

然后根据这个条件不难推知，只要矩形内部任意一个 \(2\times 2\) 的矩阵满足条件即可。
那么本问题就被转化为最大全 \(1\) 子矩阵问题。悬线法解决即可。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 2e3 + 10;
int n, m, l[N][N], r[N][N], up[N][N];
char a[N][N];

int main(){
	//FO("");
	read(n, m);
	int ans = max(n, m);
	U(i, 1, n) {
		scanf("%s", a[i] + 1);
		U(j, 1, m) a[i][j] = (a[i][j] == '#');
	}
	--n, --m;
	U(i, 1, n) U(j, 1, m) {
		a[i][j] = !(a[i][j] ^ a[i + 1][j] ^ a[i + 1][j + 1] ^ a[i][j + 1]);
		l[i][j] = r[i][j] = j;
	}

	U(i, 1, n) {
		U(j, 2, m) if (a[i][j] && a[i][j - 1]) l[i][j] = l[i][j - 1];
		D(j, m - 1, 1) if (a[i][j] && a[i][j + 1]) r[i][j] = r[i][j + 1];
		U(j, 1, m) {
			// cerr << int(a[i][j]) << " ";
			if (a[i][j]) {
				if (a[i - 1][j]) {
					chkmax(l[i][j], l[i - 1][j]);
					chkmin(r[i][j], r[i - 1][j]);
				}
				up[i][j] = up[i - 1][j] + 1;
				// cerr << up[i][j] << " " << i << " " << j << "\n";
				// if (i == 3 && j == 3) {
					// cerr << l[i][j] << " " << r[i][j] << " " << up[i][j] << "\n";
				// }
				chkmax(ans, (r[i][j] - l[i][j] + 2) * (up[i][j] + 1));
			}
		}
		// cerr << '\n';
	}

	writeln(ans);
	return 0;
}