CF480E Parking Lot（two-pointers + 单调队列优化）

题面

动态加障碍物，同时查询最大子正方形。
$n,mleq2000$

题解

加障碍不好做，直接离线后反着做，每次就是清除一个障碍物。

显然倒着做答案是递增的，而且答案的值域是$[0,min(n,m)]$，所以我们可以存一下答案，然后每次$check$能不能$+1$。

考虑把一个位置的障碍物清除后如果答案能变大，这个矩阵一定包含这个位置。那么考虑怎么求是否存在一个边长为$len$的矩形覆盖这个位置。

我们存下$l[i][j]$和$r[i][j]$，表示$(i,j)$位置向左和向右最多能扩展的距离。这个东西是可以维护的，因为每次改一个点只会影响一行$m$个数的值。直接暴力修改。

然后对于$(i,j)$位置，如果存在一个边长为$len$的正方形覆盖$(i,j)$，一定在第$j$列存在连续$len$行满足：
$min(l[k][j])+min(r[k][j])-1geq len$

这样我们就可以直接two-pointers，两个单调队列维护$l$和$r$的最小值来判断是否存在答案。

我的代码中并没有保证一定经过$(i,j)$这个点，但是这样并不会错过答案。

时间复杂度$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
", ans[i]);
}