luogu1856

P1856 [USACO5.5]矩形周长Picture

题目背景

墙上贴着许多形状相同的海报、照片。它们的边都是水平和垂直的。每个矩形图片可能部分或全部的覆盖了其他图片。所有矩形合并后的边长称为周长。

题目描述

编写一个程序计算周长。

如图1所示7个矩形。

如图2所示，所有矩形的边界。所有矩形顶点的坐标都是整数。

输入输出格式

输入格式：

输入文件的第一行是一个整数N（0<=N<5000），表示有多少个矩形。接下来N行给出了每一个矩形左下角坐标和右上角坐标（所有坐标的数值范围都在-10000到10000之间）。

输出格式：

输出文件只有一个正整数，表示所有矩形的周长。

输入输出样例

输入样例#1：

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

输出样例#1：

求周长和，不用离散的方法

记录最小值和最小值出现的个数

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 10005
int n,x1[N],y1[N],x2[N],y2[N];
struct node{int x1,x2,y,op;}line[N];
inline bool cmp(node a,node b){return a.y!=b.y?a.y<b.y:a.op>b.op;}
struct SegmentTree{int l,r,mi,sum,lazy;}Tree[N<<4];
inline void pushup(int x)
{
    if(Tree[x<<1].mi==Tree[x<<1|1].mi)Tree[x].sum=Tree[x<<1].sum+Tree[x<<1|1].sum, Tree[x].mi=Tree[x<<1].mi;
    else if(Tree[x<<1].mi<Tree[x<<1|1].mi)Tree[x].sum=Tree[x<<1].sum, Tree[x].mi=Tree[x<<1].mi;
    else Tree[x].sum=Tree[x<<1|1].sum, Tree[x].mi=Tree[x<<1|1].mi;
}
inline void ADD(int x,int v){Tree[x].lazy+=v;Tree[x].mi+=v;}
inline void pushdown(int x){ADD(x<<1,Tree[x].lazy); ADD(x<<1|1,Tree[x].lazy); Tree[x].lazy=0;}
inline void build(int l,int r,int x)
{
    Tree[x].l=l; Tree[x].r=r; Tree[x].lazy=0;
    if(l==r){Tree[x].sum=1;Tree[x].mi=0;return;}
    int mid=(l+r)>>1;build(l,mid,x<<1);build(mid+1,r,x<<1|1);pushup(x);
}
inline void updata(int l,int r,int x,int v)
{
    if(l==Tree[x].l&&Tree[x].r==r){Tree[x].lazy+=v;Tree[x].mi+=v;return;}
    if(Tree[x].lazy!=0) pushdown(x); int mid=(Tree[x].l+Tree[x].r)>>1;
    if(r<=mid)updata(l,r,x<<1,v); else if(l>mid) updata(l,r,x<<1|1,v);
    else updata(l,mid,x<<1,v), updata(mid+1,r,x<<1|1,v); pushup(x);
}
int main()
{
    int i,ans=0; scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
        line[i*2-1].x1=line[i*2].x1=x1[i]; line[i*2-1].x2=line[i*2].x2=x2[i]-1;
        line[i*2-1].y=y1[i]; line[i*2].y=y2[i]; line[i*2-1].op=1; line[i*2].op=-1;
    }n*=2;
    sort(line+1,line+n+1,cmp); build(-N,N,1);
    for(i=1;i<=n;i++)
    {
        int oo=Tree[1].sum*(Tree[1].mi==0); updata(line[i].x1,line[i].x2,1,line[i].op); ans+=abs(oo-Tree[1].sum*(Tree[1].mi==0));
    }
    for(i=1;i<=n;i++)
    {
        line[i*2-1].x1=line[i*2].x1=y1[i]; line[i*2-1].x2=line[i*2].x2=y2[i]-1;
        line[i*2-1].y=x1[i]; line[i*2].y=x2[i]; line[i*2-1].op=1; line[i*2].op=-1;
    }
    sort(line+1,line+n+1,cmp); build(-N,N,1);
    for(i=1;i<=n;i++)
    {
        int oo=Tree[1].sum*(Tree[1].mi==0); updata(line[i].x1,line[i].x2,1,line[i].op); ans+=abs(oo-Tree[1].sum*(Tree[1].mi==0));
    }
    printf("%d
",ans);
}

View Code