题目翻译给的很清楚w
这题官方给的算法是分治，但是说实话我真的不知道它和分治有什么关系……
有一个很正常的思路是先把所有修改都加上，之后先计算出来最小的情况（这个很简单，dp一下即可），之后再逐步考虑修改有什么影响。
首先如果一次修改对答案有影响的话，那么更优的矩形一定是跨过这个障碍所在的一列的。如果当前的答案是ans的话，那么我们相当于要统计，对于障碍所在的这一列，有没有一个长为ans+1的区间，使得其每一行的左右两端能拓展到ans+1.
这个好像和以前的矩形dp非常像……考虑用到悬线法，记录每个点能向左右最远拓展几个格子。之后对于合法的正方形，我们只要在这一列从上向下，用单调队列维护一下当前能拓展到的最远左右距离是多少，把与当前行距离超过ans的都去掉，之后更新答案即可。
一开始像悬线法一样处理一下左右拓展的距离，之后对于每一个修改暴力更新一下就好了。
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #include<vector> #include<map> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') #define fr friend inline #define y1 poj #define mp make_pair #define pr pair<int,int> #define fi first #define sc second #define pb push_back #define lowbit(x) x & (-x) using namespace std; typedef long long ll; const int M = 2005; const int INF = 1000000009; const double eps = 1e-7; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct node { int x,y; }a[M]; int n,m,k,le[M][M],ri[M][M],q[M],dp[M][M],cur,ans[M],kx,ky,head,tail,tmp[M]; bool pd[M][M]; char s[M]; void init() { rep(i,1,n) rep(j,1,m) { if(pd[i][j]) dp[i][j] = 0; else dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])) + 1; cur = max(cur,dp[i][j]); } rep(i,1,n) rep(j,1,m) pd[i][j] ? le[i][j] = 0 : le[i][j] = le[i][j-1] + 1; rep(i,1,n) per(j,m,1) pd[i][j] ? ri[i][j] = 0 : ri[i][j] = ri[i][j+1] + 1; } bool check(int d) { head = 1,tail = 0; rep(i,1,n) { while(head <= tail && le[q[tail]][ky] >= le[i][ky]) tail--; q[++tail] = i; while(head <= tail && q[head] <= i - d) head++; tmp[i] = le[q[head]][ky]; } head = 1,tail = 0; rep(i,1,n) { while(head <= tail && ri[q[tail]][ky] >= ri[i][ky]) tail--; q[++tail] = i; while(head <= tail && q[head] <= i - d) head++; tmp[i] += ri[q[head]][ky] - 1; } rep(i,d,n) if(tmp[i] >= d) return 1; return 0; } int main() { n = read(),m = read(),k = read(); rep(i,1,n) { scanf("%s",s+1); rep(j,1,m) if(s[j] == 'X') pd[i][j] = 1; } rep(i,1,k) a[i].x = read(),a[i].y = read(),pd[a[i].x][a[i].y] = 1; init(); per(i,k-1,1) { ans[i+1] = cur; kx = a[i+1].x,ky = a[i+1].y,pd[kx][ky] = 0; rep(j,1,m) pd[kx][j] ? le[kx][j] = 0 : le[kx][j] = le[kx][j-1] + 1; per(j,m,1) pd[kx][j] ? ri[kx][j] = 0 : ri[kx][j] = ri[kx][j+1] + 1; while(check(cur+1)) cur++; } ans[1] = cur; rep(i,1,k) printf("%d ",ans[i]); return 0; }