【2018.06.26NOIP模拟】T1纪念碑square
题目描述
2034年，纪念中学决定修建校庆100周年纪念碑，作为杰出校友的你被找了过来，帮校方确定纪念碑的选址。
纪念中学的土地可以看作是一个长为 n，宽为 m 的矩形。它由 n*m 个 1*1 的正方形组成，其中左下角的正方形的坐标为(1,1)，右上角的正方形的坐标为(n,m)。其中有一些土地已经被用来修建建筑物，每一幢建筑物都可以看做是一个左下角为(x1,y1)，右上角为(x2,y2)的矩形。
纪念碑可以看作是一个正方形。校方希望你找出一块最大的正方形区域供他们参考。
输入格式
每一组数据的第一行包含三个整数 n，m 和 p ，分别表示学校的长，宽以及建筑物的数量。
接下来的 p 行，每行包含四个整数 x1，y1，x2，y2，分别表示每一幢建筑物左下角以及右上角的坐标。
输出格式
输出一个数，表示可能的最大边长。
输入
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
输出
3
备注
【数据范围】
对于 30% 的数据，p≤1000。
对于 70% 的数据，p≤30000。
对于 100% 的数据，p≤400000；m,n≤1000000。
一开始想的是用什么单调队列什么的维护一下最大值，但后来发现如果一块空间是密闭的是修改不到的，然后这题就暴零了
正解如下：
我们可以维护两个指针l和r，记录当前在x轴上的范围
用差分的思想，把一个矩形拆成最左边的最右边的两条线段
然后我们用一颗线段树维护当前y轴上的最长连续空格maxs
当r-l+1>maxs，将l向右移动，同时记录线段的加入和删除
然后时间复杂度是O(nlog(n))" role="presentation">O(nlog(n))O(nlog(n))，又因为我们发现这道题没有查询函数，所以我们并不用下传标记，直接在修改的时候就可以向上更新答案了
#include<bits/stdc++.h>
using namespace std;
#define LD (o<<1)
#define RD ((o<<1)|1)
#define N 1000010
#define M 4000010
int n,m,p;
int x[2][N],y[2][N];
int tag[M],l[M],r[M],ls[M],rs[M],maxs[M];
vector<int> add[N],del[N];
void pushup(int o){
if(tag[o]){ls[o]=rs[o]=maxs[o]=0;return;}
if(l[o]==r[o]){ls[o]=rs[o]=maxs[o]=1;return;}
ls[o]=ls[LD]+(ls[LD]==r[LD]-l[LD]+1)*ls[RD];
rs[o]=rs[RD]+(rs[RD]==r[RD]-l[RD]+1)*rs[LD];
maxs[o]=max(rs[LD]+ls[RD],max(maxs[LD],maxs[RD]));
}
void build(int o,int ll,int rr){
l[o]=ll;r[o]=rr;
ls[o]=rs[o]=maxs[o]=rr-ll+1;
tag[o]=0;
if(ll==rr)return;
int mid=(ll+rr)>>1;
build(LD,ll,mid);
build(RD,mid+1,rr);
}
void modify(int o,int ll,int rr,int ql,int qr,int val){
if(ql<=ll&&rr<=qr){tag[o]+=val;pushup(o);return;}
int mid=(l[o]+r[o])>>1;
if(ql<=mid)modify(LD,ll,mid,ql,qr,val);
if(mid<qr)modify(RD,mid+1,rr,ql,qr,val);
pushup(o);
}
void out_put(int o){
cout<<o<<" "<<l[o]<<" "<<r[o]<<" "<<maxs[o]<<endl;
if(l[o]==r[o])return;
out_put(LD);
out_put(RD);
}
int main(){
// freopen("square.in","r",stdin);
// freopen("square.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=p;i++){
scanf("%d%d%d%d",&x[0][i],&y[0][i],&x[1][i],&y[1][i]);
add[x[0][i]].push_back(i);
del[x[1][i]].push_back(i);
}
build(1,1,m);
int ans=0,l=1,r=1;
while(r<=n){
for(int it=0;it<add[r].size();it++)
modify(1,1,m,y[0][add[r][it]],y[1][add[r][it]],1);
ans=max(ans,min(maxs[1],r-l+1));
while(maxs[1]<r-l+1){
for(int it=0;it<del[l].size();it++)
modify(1,1,m,y[0][del[l][it]],y[1][del[l][it]],-1);
l++;
}
r++;
// out_put(1);
}
printf("%d",ans);
return 0;
}