【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

输出

备注

【数据范围】

对于 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;

}

巴特西

【2018.06.26NOIP模拟】T1纪念碑square 【线段树】*

【2018.06.26NOIP模拟】T1纪念碑square

题目描述

输入格式

输出格式

输入

输出

备注

最新文章

热门文章