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.

Solution

• 套路——掃描線+線段樹。

• 將一個矩形（橫坐標 x1,x2）拆成加入 x1 和 刪除 x2+1 兩部分。

• 按橫坐標排序，用兩個指針 l,r 掃，同時用線段樹維護當前區間中的最大空位置長度。

• 方法：區間維護最大長度，從左延伸最大長度、從右延伸最大長度……

• 設最大空位置長度為 ms ，若 ms<r?l+1 ，則讓 l 右移，否則 r 右移即可。

• 時間復雜度為 O(N?log?N) 。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; const int N=1e6+5; struct data {int x,y1,y2,z; }a[N]; struct node {int mx,l,r,c; }f[N<<2]; int qx,qy,qz,ans,tot; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline bool cmp(data x,data y) {return x.x<y.x; } inline int max(int x,int y) {return x>y?x:y; } inline int min(int x,int y) {return x<y?x:y; } inline void update(int v,int l,int r) {int ls=v<<1,rs=v<<1|1,mid=l+r>>1;f[v].l=f[ls].l,f[v].r=f[rs].r;if(f[ls].l==mid-l+1) f[v].l+=f[rs].l;if(f[rs].r==r-mid) f[v].r+=f[ls].r;f[v].mx=max(f[ls].mx,f[rs].mx);f[v].mx=max(f[v].mx,f[ls].r+f[rs].l); } void make(int v,int l,int r) {f[v].mx=f[v].l=f[v].r=r-l+1;if(l==r) return;int mid=l+r>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r); } void change(int v,int l,int r) {if(qx<=l && r<=qy){f[v].c+=qz;if(!f[v].c){if(l==r) f[v].mx=f[v].l=f[v].r=1; else update(v,l,r);}else f[v].mx=f[v].l=f[v].r=0;return;}int mid=l+r>>1;if(qx<=mid) change(v<<1,l,mid);if(qy>mid) change(v<<1|1,mid+1,r);if(!f[v].c) update(v,l,r); else f[v].mx=f[v].l=f[v].r=0; } int main() {int n=read(),m=read(),p=read();for(int i=1;i<=p;i++){int x1=read(),y1=read(),x2=read(),y2=read();a[++tot].x=x1,a[tot].y1=y1,a[tot].y2=y2,a[tot].z=1;a[++tot].x=x2+1,a[tot].y1=y1,a[tot].y2=y2,a[tot].z=-1;}sort(a+1,a+1+tot,cmp);make(1,1,m);int l=1,r=1,nl=1,nr=1;while(a[nl].x==l){if(a[nl].z==-1){qx=a[nl].y1,qy=a[nl].y2,qz=a[nl].z;change(1,1,m);}nl++;}while(a[nr].x==r){if(a[nr].z==1){qx=a[nr].y1,qy=a[nr].y2,qz=a[nr].z;change(1,1,m);}nr++;}while(r<=n){ans=max(ans,min(f[1].mx,r-l+1));if(r-l+1<=f[1].mx){r++;while(a[nr].x==r){if(a[nr].z==1){qx=a[nr].y1,qy=a[nr].y2,qz=a[nr].z;change(1,1,m);}nr++;}}else{l++;while(a[nl].x==l){if(a[nl].z==-1){qx=a[nl].y1,qy=a[nl].y2,qz=a[nl].z;change(1,1,m);}nl++;}}}printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 4238. 【五校联考5day2】纪念碑的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。