JZOJ4238 纪念碑

Description

2034年,纪念中学决定修建校庆100周年纪念碑,作为杰出校友的你被找了过来,帮校方确定纪念碑的选址.

纪念中学的土地可以看作是一个长为n,宽为m的矩形.它由n* m个1*1的正方形组成,其中左下角的正方形的坐标为(1,1),右上角的正方形的坐标为(n, m).其中有一些土地已经被用来修建建筑物,每一幢建筑物都可以看做是一个左下角为(x1,y1),右上角为(x2,y2)的矩形.

纪念碑可以看作是一个正方形.校方希望你找出一块最大的正方形区域供他们参考.

Input

每一组数据的第一行包含三个整数n,m和p,分别表示学校的长,宽以及建筑物的数量.

接下来的p行,每行包含四个整数x1,y1,x2,y2,分别表示每一幢建筑物左下角以及右上角的坐标.

Output

输出一个数,表示可能的最大边长.

Sample Input

13 5 8

8 4 10 4

4 3 4 4

10 2 12 2

8 2 8 4

2 4 6 4

10 3 10 4

12 3 12 4

2 2 4 2

Sample Output

3

Data Constraint

对于30%的数据,p<=1000.

对于70%的数据,p<=30000.

对于100%的数据,p<=400000,m,n<=1000000.

分析：

如果我们确定了上下界，那么左右界最大就可以用线段树维护

设mx为整个区间最长空段，lmx为左端点出发最长空段，rmx为右端点出发最长空段

这三个值可以进行懒标记维护并向上递推

上下界考虑扫描线

目前上下界为L和R，最长左右界为S

考虑拓宽R，如果R-L+1>=S，则可以拓宽R

否则便缩小L，帮助拓宽R

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#define maxn 1000005

#define pii pair<int,int>

#define mp make_pair

using namespace std;

inline int getint()

{

	int num=0,flag=1;char c;

	while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;

	while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();

	return num*flag;

}

int n,m;

int len[maxn<<2],lmx[maxn<<2],rmx[maxn<<2],mx[maxn<<2],lz[maxn<<2];

vector<pii>l[maxn],r[maxn];

int ans;

inline void pushup(int i)

{

	mx[i]=max(max(mx[i<<1],mx[i<<1|1]),rmx[i<<1]+lmx[i<<1|1]);

	lmx[i]=(lmx[i<<1]==len[i<<1]?len[i<<1]+lmx[i<<1|1]:lmx[i<<1]);

	rmx[i]=(rmx[i<<1|1]==len[i<<1|1]?len[i<<1|1]+rmx[i<<1]:rmx[i<<1|1]);

}

inline void work(int i,int x){mx[i]=lmx[i]=rmx[i]=x;}

inline void pushdown(int i)

{

	if(lz[i])

	{

		if(~lz[i])lz[i<<1|1]=lz[i<<1]=lz[i],work(i<<1,0),work(i<<1|1,0);

		else lz[i<<1|1]=lz[i<<1]=lz[i],work(i<<1,len[i<<1]),work(i<<1|1,len[i<<1|1]);

		lz[i]=0;

	}

}

inline void build(int i,int l,int r)

{

	mx[i]=lmx[i]=rmx[i]=len[i]=r-l+1;

	if(l==r)return;

	int mid=(l+r)>>1;

	build(i<<1,l,mid),build(i<<1|1,mid+1,r);

}

inline void update(int i,int l,int r,int ql,int qr,int op)

{

	if(qr<l||r<ql)return;

	if(ql<=l&&r<=qr)

	{

		if(~op)work(i,0),lz[i]=op;

		else work(i,len[i]),lz[i]=op;

		return;

	}

	pushdown(i);

	int mid=(l+r)>>1;

	update(i<<1,l,mid,ql,qr,op),update(i<<1|1,mid+1,r,ql,qr,op);

	pushup(i);

}

int main()

{

	n=getint(),m=getint();int tmp=getint();

	while(tmp--)

	{

		int x1=getint(),y1=getint(),x2=getint(),y2=getint();

		l[x1].push_back(mp(y1,y2)),r[x2].push_back(mp(y1,y2));

	}

	build(1,1,m);

	int L=1;

	for(int R=1;R<=n;R++)

	{

		for(int i=0;i<l[R].size();i++)update(1,1,m,l[R][i].first,l[R][i].second,1);

		ans=max(ans,min(mx[1],R-L+1));

		while(R-L+1>mx[1])

		{

			for(int i=0;i<r[L].size();i++)update(1,1,m,r[L][i].first,r[L][i].second,-1);

			L++;

		}

	}

	printf("%d\n",ans);

}

巴特西

JZOJ4238 纪念碑

最新文章

热门文章