题意：给一个$n\times m$的网格，初始时有些地方不能选，给$k$个询问$(x,y)$，每次令$(x,y)$不能选，然后询问最大子正方形的边长
如果按原题来做，禁止选一个点对答案的影响是极其鬼畜的，不方便统计，所以我们离线倒序处理，先让所有询问的点不能选，然后反过来逐次让某些点可选，这样答案是不减的，而且更优的答案一定包含此次选的点
预处理出$up_{i,j}$表示$(i,j)$往上走最远可到的'.'，$down_{i,j}$表示$(i,j)$往下走最远可到的'.'
于是对于某行，我们可以扫一遍求出所有跨越此行的正方形的最大边长
假设当前处理到此行的$[l,r]$，已经求得区间中$up$和$down$的最值
①若区间包含'X'或$\left|up-down\right|\lt r-l$，左端点++
②否则更新答案并右端点++
右端点移动时直接$O(1)$更新最值
左端点移动时用线段树$O(log_2n)$更新最值
整个过程是$O(nlog_2n)$的
所以每次加入一个可选点时，暴力更新这一列的$up,down$，统计这一行的答案并更新
需要访问单点值，所以用ZKW线段树又快又方便
#include<stdio.h>
#define inf 2147483647
char s[2010][2010];
int x[2010],y[2010],up[2010][8010],ans[2010],down[2010][8010],M,m;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void pu(int id,int x){
up[id][x]=max(up[id][x<<1],up[id][x<<1|1]);
}
void pd(int id,int x){
down[id][x]=min(down[id][x<<1],down[id][x<<1|1]);
}
int queryu(int id,int s,int t){
int c=-inf;
for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
if(~s&1)c=max(c,up[id][s^1]);
if(t&1)c=max(c,up[id][t^1]);
}
return c;
}
void modifyu(int id,int p,int v){
p+=M;
for(up[id][p]=v;p>>=1;)pu(id,p);
}
int queryd(int id,int s,int t){
int c=inf;
for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
if(~s&1)c=min(c,down[id][s^1]);
if(t&1)c=min(c,down[id][t^1]);
}
return c;
}
void modifyd(int id,int p,int v){
p+=M;
for(down[id][p]=v;p>>=1;)pd(id,p);
}
int getline(int x){
int l,r,maxy,miny,res;
res=0;
for(l=r=1;l<=m;l++){
if(l>r){
r++;
l--;
continue;
}
maxy=queryu(x,l,r);
miny=queryd(x,l,r);
while(maxy!=inf&&miny!=-inf&&miny-maxy>=r-l&&r<m){
res=max(res,r-l+1);
r++;
maxy=max(maxy,up[x][r+M]);
miny=min(miny,down[x][r+M]);
}
if(r==m){
if(maxy!=inf&&miny!=-inf&&miny-maxy>=r-l)res=max(res,r-l+1);
break;
}
}
return res;
}
int main(){
int n,q,i,j;
scanf("%d%d%d",&n,&m,&q);
for(M=1;M<m+1;M<<=1);
for(i=1;i<=n;i++)scanf("%s",s[i]+1);
for(i=1;i<=q;i++){
scanf("%d%d",x+i,y+i);
s[x[i]][y[i]]='X';
}
for(i=1;i<=m;i++)s[0][i]=s[n+1][i]='X';
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(s[i][j]!='X'){
if(s[i-1][j]=='X')
up[i][j+M]=i;
else
up[i][j+M]=up[i-1][j+M];
}else
up[i][j+M]=inf;
}
}
for(i=n;i>0;i--){
for(j=1;j<=m;j++){
if(s[i][j]!='X'){
if(s[i+1][j]=='X')
down[i][j+M]=i;
else
down[i][j+M]=down[i+1][j+M];
}else
down[i][j+M]=-inf;
}
}
for(i=1;i<=n;i++){
for(j=M-1;j>0;j--){
pd(i,j);
pu(i,j);
}
}
ans[q]=0;
for(i=1;i<=n;i++)ans[q]=max(ans[q],getline(i));
for(i=q;i>1;i--){
s[x[i]][y[i]]='.';
for(j=x[i];j<=n;j++){
if(s[j][y[i]]!='X'){
if(s[j-1][y[i]]=='X')
modifyu(j,y[i],j);
else
modifyu(j,y[i],up[j-1][y[i]+M]);
}
}
for(j=x[i];j>0;j--){
if(s[j][y[i]]!='X'){
if(s[j+1][y[i]]=='X')
modifyd(j,y[i],j);
else
modifyd(j,y[i],down[j+1][y[i]+M]);
}
}
ans[i-1]=max(ans[i],getline(x[i]));
}
for(i=1;i<=q;i++)printf("%d\n",ans[i]);
}