学步园

传送门：【codeforces】480E Parking Lot

题目分析：很早以前在同学助攻下写出来的，想想还是放出来好了，是个不错的思想。

原题是在动态将可行区域变成不可行区域的同时求全局最大子正方形，n，m，k至多2000。

既然只有加点，于是我们离线，倒着来，这样便只有删点。

我们给每个节点（i,j）保存它向上能延伸的距离U[i][j]以及向下能延伸的距离D[i][j]。

易知删除一个点最多影响一列上的U和D，暴力更新U，D。复杂度为O（n^2），可以承受。

首先我们预处理出所有点都加上后的最大子正方形（直接dp）。

然后建立一棵线段树，线段树保存一段区间向下延伸的最大子矩形的高度（即最小的D），同时保存一段区间向上延伸的最大子矩形的高度（即最小的U）。

每次删点时我们暴力维护U，D，然后对删点的那一行建立线段树进行最大子正方形大小的维护（最大子正方形大小的改变一定和这一行上的点有关）。

维护方法直接见代码好了。

然后查询就是O（1）的操作了。

觉得这解题的思想很不错，值得思考~

而且这题的解法貌似很多的样子。。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define For( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define root 1 , 1 , m

const int MAXN = 2005 ;
const int INF = 0x3f3f3f3f ;

struct Node {
	int x , y ;
} p[MAXN] ;

int minu[MAXN << 2] , mind[MAXN << 2] ;
int G[MAXN][MAXN] ;
int U[MAXN][MAXN] ;
int D[MAXN][MAXN] ;
int left[MAXN] , right[MAXN] ;
int ans[MAXN] ;
int n , m , k ;

int min1 , min2 ;
void query ( int L , int R , int o , int l , int r ) {
	if ( L <= l && r <= R ) {
		min1 = min ( min1 , minu[o] ) ;
		min2 = min ( min2 , mind[o] ) ;
		return ;
	}
	int m = mid ;
	if ( L <= m ) query ( L , R , lson ) ;
	if ( m <  R ) query ( L , R , rson ) ;
}

void build ( int x , int o , int l , int r ) {
	if ( l == r ) {
		minu[o] = U[x][l] ;
		mind[o] = D[x][l] ;
		return ;
	}
	int m = mid ;
	build ( x , lson ) ;
	build ( x , rson ) ;
	minu[o] = min ( minu[ls] , minu[rs] ) ;
	mind[o] = min ( mind[ls] , mind[rs] ) ;
}

int calc () {
	int ans = 0 ;
	For ( i , 1 , n ) {
		For ( j , 1 , m ) {
			int x = j ;
			while ( x > 1 && U[i][x - 1] >= U[i][j] ) x = left[x - 1] ;
			left[j] = x ;
		}
		rev ( j , m , 1 ) {
			int x = j ;
			while ( x < m && U[i][x + 1] >= U[i][j] ) x = right[x + 1] ;
			right[j] = x ;
		}
		For ( j , 1 , m ) {
			ans = max ( ans , min ( U[i][j] , right[j] - left[j] + 1 ) ) ;
			//printf ( "%d %d %d\n" , U[i][j] , left[j] , right[j] ) ;
		}
		//printf ( "%d\n" , ans ) ;
	}
	return ans ;
}

int check ( int size , int y ) {
	if ( size > n || size > m ) return 0 ;
	For ( i , max ( 1 , y - size + 1 ) , m - size + 1 ) {
		min1 = min2 = INF ;
		query ( i , i + size - 1 , root ) ;
		if ( min1 + min2 - 1 >= size ) return 1 ;
	}
	return 0 ;
}

void solve () {
	clr ( U , 0 ) ;
	clr ( D , 0 ) ;
	clr ( G , 0 ) ;
	clr ( ans , 0 ) ;
	For ( i , 1 , n ) {
		getchar () ;
		For ( j , 1 , m ) {
			char c = getchar () ;
			G[i][j] = c == '.' ;
		}
	}
	rep ( i , 0 , k ) {
		scanf ( "%d%d" , &p[i].x , &p[i].y ) ;
		G[p[i].x][p[i].y] = 0 ;
	}
	//For ( i , 1 , n ) For ( j , 1 , m ) printf ( "%d%c" , G[i][j] , j < m ? ' ' : '\n' ) ;
	For ( i , 1 , n ) For ( j , 1 , m ) U[i][j] = G[i][j] ? U[i - 1][j] + 1 : 0 ;
	rev ( i , n , 1 ) For ( j , 1 , m ) D[i][j] = G[i][j] ? D[i + 1][j] + 1 : 0 ;
	int size = calc () ;
	rev ( i , k - 1 , 0 ) {
		ans[i] = size ;
		if ( !i ) break ;
		int x = p[i].x ;
		int y = p[i].y ;
		G[x][y] = 1 ;
		U[x][y] = U[x - 1][y] + 1 ;
		For ( j , x + 1 , n ) {
			if ( !G[j][y] ) break ;
			U[j][y] += U[x][y] ;
		}
		D[x][y] = D[x + 1][y] + 1 ;
		rev ( j , x - 1 , 1 ) {
			if ( !G[j][y] ) break ;
			D[j][y] += D[x][y] ;
		}
		build ( x , root ) ;
		while ( check ( size + 1 , y ) ) ++ size ;
	}
	rep ( i , 0 , k ) printf ( "%d\n" , ans[i] ) ;
}

int main () {
	while ( ~scanf ( "%d%d%d" , &n , &m , &k ) ) solve () ;
	return 0 ;
}