12265 - Selling Land(单调队列)(二)
m, up[N][N], ans[2 * N]; char str[N]; void solve() { memset(ans, 0, sizeof(ans)); for (int i = 1; i <= n; i++) { deque
Q; for (int j = 1; j <= m; j++) { int r = j; while (!Q.empty() && Q.back().first >= up[i][j]) { r = Q.back().second; Q.pop_back(); } if (up[i][j] == 0) continue; if (Q.empty() || up[i][j] - Q.back().first > r - Q.back().second) { ans[up[i][j] + j - r + 1]++; Q.push_back(make_pair(up[i][j], r)); } else ans[j - Q.back().second + 1 + Q.back().first]++; } } for (int k = 2; k <= n + m; k++) if (ans[k]) printf("%d x %d\n", ans[k], k * 2); } int main() { scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%s", str + 1); for (int j = 1; j <= m; j++) { if (str[j] == '#') up[i][j] = 0; else up[i][j] = up[i - 1][j] + 1; } } solve(); } return 0; }