在维护高度递增的单调栈中，同时维护周长递增（这一点是很容易证明的），就可以用O(n^2)的复杂度解决了。
代码：
#include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define lson o<<1 #define rson o<<1|1 #define CLR(A, X) memset(A, X, sizeof(A)) using namespace std; typedef long long LL; typedef pair<int, int> PII; const double eps = 1e-10; int dcmp(int x){if(fabs(x)<eps) return 0; return x<0?-1:1;} const int N = 1e3+5; const LL MOD = 1e9+7; char mp[N][N]; int h[N], num[2*N]; PII s[N]; int main() { int T; cin >> T; while(T--) { CLR(num, 0); CLR(h, 0); int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%s", mp[i]+1); for(int i = 1; i <= n; i++) { int top = -1; for(int j = 1; j <= m; j++) { if(mp[i][j] == '#') { h[j] = 0; top = -1; continue; } h[j]++; PII x = {j, h[j]}; while(top>=0 && s[top].se>=x.se) x.fi = s[top--].fi; if(top<0 || s[top].se-s[top].fi<x.se-x.fi) s[++top] = x; x = s[top]; num[x.se-x.fi+j+1]++; } } for(int i = 1; i <= n+m; i++) if(num[i]) { printf("%d x %d\n", num[i], i<<1); } } return 0; }