题面
动态加障碍物，同时查询最大子正方形。
n,m≤2000n,m\leq2000n,m≤2000
题解
加障碍不好做，直接离线后反着做，每次就是清除一个障碍物。
显然倒着做答案是递增的，而且答案的值域是[0,min(n,m)][0,\min(n,m)][0,min(n,m)]，所以我们可以存一下答案，然后每次checkcheckcheck能不能+1+1+1。
考虑把一个位置的障碍物清除后如果答案能变大，这个矩阵一定包含这个位置。那么考虑怎么求是否存在一个边长为lenlenlen的矩形覆盖这个位置。
我们存下l[i][j]l[i][j]l[i][j]和r[i][j]r[i][j]r[i][j]，表示(i,j)(i,j)(i,j)位置向左和向右最多能扩展的距离。这个东西是可以维护的，因为每次改一个点只会影响一行mmm个数的值。直接暴力修改。
然后对于(i,j)(i,j)(i,j)位置，如果存在一个边长为lenlenlen的正方形覆盖(i,j)(i,j)(i,j)，一定在第jjj列存在连续lenlenlen行满足：
min(l[k][j])+min(r[k][j])−1≥len\min(l[k][j])+\min(r[k][j])-1\geq lenmin(l[k][j])+min(r[k][j])−1≥len
这样我们就可以直接two-pointers，两个单调队列维护lll和rrr的最小值来判断是否存在答案。
我的代码中并没有保证一定经过(i,j)(i,j)(i,j)这个点，但是这样并不会错过答案。
时间复杂度O(nm)O(nm)O(nm)
CODE
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int n, m, k, l[MAXN][MAXN], r[MAXN][MAXN];
char S[MAXN];
int a[MAXN][MAXN], dp[MAXN][MAXN], x[MAXN], y[MAXN], ans[MAXN];
void clr(int i) {
for(int j = 1; j <= m; ++j) l[i][j] = a[i][j] ? 0 : l[i][j-1] + 1;
for(int j = m; j >= 1; --j) r[i][j] = a[i][j] ? 0 : r[i][j+1] + 1;
}
int solve() {
int re = 0;
for(int i = 1; i <= n; ++i) clr(i);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(!a[i][j]) {
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
re = max(re, dp[i][j]);
}
return re;
}
int v[2][MAXN], q[2][MAXN], s[2], t[2];
inline void del(int p) {
while(s[0] < t[0] && q[0][s[0]] <= p) ++s[0];
while(s[1] < t[1] && q[1][s[1]] <= p) ++s[1];
}
inline void ins(int i) {
while(s[0] < t[0] && v[0][q[0][t[0]-1]] >= v[0][i]) --t[0]; q[0][t[0]++] = i;
while(s[1] < t[1] && v[1][q[1][t[1]-1]] >= v[1][i]) --t[1]; q[1][t[1]++] = i;
}
bool calc(int j, int len) {
for(int i = 1; i <= n; ++i) v[0][i] = l[i][j], v[1][i] = r[i][j];
s[0] = s[1] = t[0] = t[1] = 0;
q[0][0] = q[1][0] = 0;
for(int i = 1, p = 0; i <= n; ++i) {
while(i-p >= len) del(p++); ins(i);
if(i >= len && v[0][q[0][s[0]]] + v[1][q[1][s[1]]] - 1 >= len) return 1;
}
return 0;
}
int main () {
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; ++i) {
scanf("%s", S+1);
for(int j = 1; j <= m; ++j)
a[i][j] = S[j] == 'X';
}
for(int i = 1; i <= k; ++i) scanf("%d%d", &x[i], &y[i]), a[x[i]][y[i]] = 1;
ans[k] = solve();
for(int i = k; i > 1; --i) {
a[x[i]][y[i]] = 0;
clr(x[i]);
for(ans[i-1]=ans[i]; calc(y[i], ans[i-1]+1); ++ans[i-1]);
}
for(int i = 1; i <= k; ++i) printf("%d\n", ans[i]);
}