[蓝桥杯 2017 省 A] 油漆面积

题目描述

X 星球的一批考古机器人正在一片废墟上考古。

该区域的地面坚硬如石、平整如镜。

管理人员为方便，建立了标准的直角坐标系。

每个机器人都各有特长、身怀绝技。它们感兴趣的内容也不相同。

经过各种测量，每个机器人都会报告一个或多个矩形区域，作为优先考古的区域。

矩形的表示格式为 $(x_1,y_1,x_2,y_2)$，代表矩形的两个对角点坐标。

为了醒目，总部要求对所有机器人选中的矩形区域涂黄色油漆。

小明并不需要当油漆工，只是他需要计算一下，一共要耗费多少油漆。

其实这也不难，只要算出所有矩形覆盖的区域一共有多大面积就可以了。

注意，各个矩形间可能重叠。

本题的输入为若干矩形，要求输出其覆盖的总面积。

输入格式

第一行，一个整数 $n$，表示有多少个矩形 $(1\le n<10000)$。

接下来的 $n$ 行，每行有 $4$ 个整数 $x_1$，$y_1$，$x_2$，$y_2$，空格分开，表示矩形的两个对角顶点坐标。

$(0\le x_1,y_1,x_2,y_2\le 10000)$。

输出格式

一行一个整数，表示矩形覆盖的总面积。

样例 #1

样例输入 #1

3
1 5 10 10
3 1 20 20
2 7 15 17

样例输出 #1

340

样例 #2

样例输入 #2

3
5 2 10 6
2 7 12 10
8 1 15 15

样例输出 #2

128

提示

蓝桥杯 2022 省赛 A 组 J 题。

Java代码一

这个是看了 $Acwing$ 题解之后写的代码，但始终不理解第 $55$ 行 $y2$ 为什么要减一

import java.util.*;
class Main
{
    public static int N = 10010;
    static class Segment   //扫描线
    {
        int x;
        int y1;
        int y2;
        int k;  //起始边为1,终止边为-1;
    }
    static class Tr
    {
        int l;
        int r;
        int cnt;    //该区域重叠次数
        int len;    //该区域y轴长度
    }
    static class Cmp implements Comparator<Segment>
    {
        public int compare(Segment seg1, Segment seg2)
        {
            return seg1.x-seg2.x;
        }
    }
    public static Segment[] seg = new Segment[2*N];
    public static Tr[] tr = new Tr[4*N];
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int m=0;    //用于记录扫描线的个数
        for(int i=0;i<n;i++)
        {
            int x1=sc.nextInt(),y1=sc.nextInt(),x2=sc.nextInt(),y2=sc.nextInt();
            seg[m]=new Segment();   //某矩形的起始扫描线
            seg[m].x=x1;
            seg[m].y1=y1;
            seg[m].y2=y2;
            seg[m++].k=1;
            seg[m]=new Segment();   //某矩形的终止扫描线
            seg[m].x=x2;
            seg[m].y1=y1;
            seg[m].y2=y2;
            seg[m++].k=-1;
        }
        Arrays.sort(seg,0,m,new Cmp());   //扫描线排序,注意一定是0到m,不要写0到2*N
        for(int i=0;i<4*N;i++)  tr[i]=new Tr();
        build(1,0,N);
        
        int res=0;  //面积
        for(int i=0;i<m;i++)
        {
            if(i>0) res+=tr[1].len*(seg[i].x-seg[i-1].x);   //从第二条扫描线开始
            modify(1,seg[i].y1,seg[i].y2-1,seg[i].k);   //这里y2需要减一
        }
        System.out.println(res);
    }
    public static void build(int x,int l,int r)
    {
        tr[x].l=l;
        tr[x].r=r;
        if(l==r)    return;
        int mid=l+r>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
    }
    public static void modify(int x,int l,int r,int k)
    {
        if(l<=tr[x].l && tr[x].r<=r)  //如果包含该节点
        {
            tr[x].cnt+=k;
            pushup(x);
        }
        else    //报错Index 65569 out of bounds for length 40040是因为这里没写else
        {
            int mid=tr[x].l+tr[x].r>>1;
            if(l<=mid)  modify(x<<1,l,r,k);
            if(r>mid)   modify(x<<1|1,l,r,k);
            pushup(x);
        }
    }
    public static void pushup(int x)
    {
        if(tr[x].cnt>0) tr[x].len=tr[x].r-tr[x].l+1;
        else if(tr[x].l==tr[x].r)   tr[x].len=0;    //叶节点
        else    tr[x].len=tr[x<<1].len+tr[x<<1|1].len;
    }
}

Java代码二

后来经过不断地查资料，找到了下图

原文链接 1228. 油漆面积 ，原来是我对线段树还理解不到位才导致的这个错误，看了这个图之后恍然大悟，写下了代码二成功 $AC$

import java.util.*;
class Main
{
    public static int N = 10010;
    static class Segment   //扫描线
    {
        int x;
        int y1;
        int y2;
        int k;  //起始边为1,终止边为-1;
    }
    static class Tr
    {
        int l;
        int r;
        int cnt;    //该区域重叠次数
        int len;    //该区域y轴长度
    }
    static class Cmp implements Comparator<Segment>
    {
        public int compare(Segment seg1, Segment seg2)
        {
            return seg1.x-seg2.x;
        }
    }
    public static Segment[] seg = new Segment[2*N];
    public static Tr[] tr = new Tr[8*N];	//这里4*N不够用
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int m=0;    //用于记录扫描线的个数
        for(int i=0;i<n;i++)
        {
            int x1=sc.nextInt(),y1=sc.nextInt(),x2=sc.nextInt(),y2=sc.nextInt();
            seg[m]=new Segment();   //某矩形的起始扫描线
            seg[m].x=x1;
            seg[m].y1=y1;
            seg[m].y2=y2;
            seg[m++].k=1;
            seg[m]=new Segment();   //某矩形的终止扫描线
            seg[m].x=x2;
            seg[m].y1=y1;
            seg[m].y2=y2;
            seg[m++].k=-1;
        }
        Arrays.sort(seg,0,m,new Cmp());   //扫描线排序,注意一定是0到m,不要写0到2*N
        for(int i=0;i<8*N;i++)  tr[i]=new Tr();
        build(1,0,N);
        
        int res=0;  //面积
        for(int i=0;i<m;i++)
        {
            if(i>0) res+=tr[1].len*(seg[i].x-seg[i-1].x);   //从第二条扫描线开始
            modify(1,seg[i].y1,seg[i].y2,seg[i].k);
        }
        System.out.println(res);
    }
    public static void build(int x,int l,int r)
    {
        tr[x].l=l;
        tr[x].r=r;
        if(l==r-1)    return;   //叶节点宽度为2
        int mid=l+r>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid,r);
    }
    public static void modify(int x,int l,int r,int k)
    {
        if(tr[x].l>=r || tr[x].r<=l)    return;
        if(l<=tr[x].l && tr[x].r<=r)  //如果包含该节点
        {
            tr[x].cnt+=k;
            pushup(x);
        }
        else    //报错Index 65569 out of bounds for length 40040是因为这里没写else
        {
            int mid=tr[x].l+tr[x].r>>1;
            if(l<=mid)  modify(x<<1,l,r,k);
            if(r>mid)   modify(x<<1|1,l,r,k);
            pushup(x);
        }
    }
    public static void pushup(int x)
    {
        if(tr[x].cnt>0) tr[x].len=tr[x].r-tr[x].l;
        else if(tr[x].l==tr[x].r)   tr[x].len=0;    //叶节点
        else    tr[x].len=tr[x<<1].len+tr[x<<1|1].len;
    }
}

个人理解

扫描线和线段树解题在这里不做过多赘述，网上有很多题解，这里主要是想要说明 $y2$ 为什么需要减一的问题，读者可以举个例子自行按照代码一和二分别推演一遍即可理解原因，希望这篇文章能够帮到一些同样有这个疑问的后人