[CF480E]Parking Lot

题意：给一个$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]);
}

巴特西

[CF480E]Parking Lot

最新文章

热门文章