题目描述

墙上粘贴了n个相同形状的矩形海报。

它们的边都是垂直或水平的。

每个矩形可以被其他矩形部分或完全覆盖。

所有矩形的并集边界的长度称为周长。

现在请你编程计算这个周长是多少。

图1显示了一个包含7个矩形的图形样例：

图2给出了它的并集边界：

每个矩形的顶点都有一个整数坐标。

输入格式
第一行输入整数n，表示矩形的数量。

接下来n行，每行四个整数x1,y1,x2,y2用以描述一个矩形,(x1,y1)为矩形的左下角坐标，(x2,y2)为矩形的右上角坐标。

输出格式
输出一个整数，表示矩形并集的周长。

数据范围

0 ≤ n < 5000,
−10000 ≤ xi,yi ≤10000

输入样例：

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

输出样例：

228

这题是扫描线求周长的模板题，学了两个下午了。。。
解这题的心路历程：
 1.线段树的维护多了左右端点有没有被覆盖的bool数据，区间内有多少条线段segNum；
 2.pushUp函数开始不怎么理解，原来看成是点的（第二个判断条件成立）是该点代表
的区间被取消覆盖，而求面积的话取消只是该段区间的覆盖次数变为了零，与求周长略
有不同；
 3.左右端点有没有被覆盖：考虑至最小单元，即被离散化的数据的每个单元，扫描线
一定会以某一个单元为起点到往后X个单元为终点（X>=0）为终点停止，所以这些单元可以
非常容易地确定端点是被覆盖的，而凌驾与这些单元之上的父节点，就可以通过这些基础单元
端点覆盖情况确定出它本身的覆盖情况，这样做的主要目的是求周长（与扫描线垂直方向的边总和）
 4.没有爆long long，

C++ 代码

#include<iostream>
#include<algorithm>
#include<cmath>
#define Lson (root<<1)
#define Rson (root<<1|1)
//#define int long long

const int offset = 1e4 + 0, space = 5e3 + 7;
int N;
struct kk { int y, rightX, leftX, whi; bool operator <(kk& _RHS)const { if (y == _RHS.y)return whi > _RHS.whi; else return y < _RHS.y; } };
struct kl{
    int left, right,len;
    int coverNum;
    bool leftCover, rightCover;//左右端点是否被覆盖
    int segNum;//区间有多少条线段
}love[space<<4];
struct kk ali[space << 1];
int discrete[space << 2] = {}, num = 0, ans = 0;

void buildTree(int root, int left, int right)
{
    love[root] = { left,right,0,false,false,0 };
    if (left == right)return;
    int mid = (left + right) >> 1;
    buildTree(Lson, left, mid), buildTree(Rson, mid + 1, right);
}

void pushUp(int root)
{
    if (love[root].coverNum)
    {
        love[root].leftCover = love[root].rightCover = 1;
        love[root].len = discrete[love[root].right + 1] - discrete[love[root].left];
        love[root].segNum = 1;
    }
    else if (love[root].left == love[root].right)
    {
        love[root].leftCover = love[root].rightCover = 0;
        love[root].len = 0;
        love[root].segNum = 0;
    }
    else
    {
        love[root].leftCover = love[Lson].leftCover;
        love[root].rightCover = love[Rson].rightCover;
        love[root].len = love[Lson].len + love[Rson].len;
        love[root].segNum = love[Lson].segNum + love[Rson].segNum - (love[Lson].rightCover & love[Rson].leftCover);
    }

}

void update(int root, int left, int right, int whi)
{
    int l = love[root].left, r = love[root].right;
    int mid = (l + r) >> 1;

    if (left <= l && right >= r)
    {
        love[root].coverNum += whi;
        pushUp(root);
        return;
    }
    if (left <= mid)update(Lson, left, right, whi);
    if (right > mid)update(Rson, left, right, whi);
    pushUp(root);
}


signed main(void)
{
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
    std::cin >> N;
    for (int i = 1; i <= N; i++)
    {
        //int y, rightX, leftX, whi
        int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        x1 += offset, y1 += offset, x2 += offset, y2 += offset;
        discrete[++num] = x1, discrete[++num] = x2;
        ali[i * 2 - 1] = { y1,x2,x1,1 };
        ali[i << 1] = { y2,x2,x1,-1 };
    }

    std::sort(discrete + 1, discrete + 1 + num);
    num = std::unique(discrete + 1, discrete + 1 + num) - discrete - 1;
    std::sort(ali + 1, ali + 1 + (N << 1));

    //离散：
    for (int i = 1; i <= N << 1; i++)
    {
        int pos1 = std::lower_bound(discrete + 1, discrete + 1 + num, ali[i].leftX) - discrete;
        int pos2 = std::lower_bound(discrete + 1, discrete + 1 + num, ali[i].rightX) - discrete;
        ali[i].leftX = pos1, ali[i].rightX = pos2;
    }

    buildTree(1, 1, num);

    int pre = 0;
    for (int i = 1; i <= N << 1; i++)
    {
        update(1, ali[i].leftX, ali[i].rightX - 1, ali[i].whi);
        ans += abs(love[1].len - pre);
        //竖线：[下一条横线的高度-现在这条横线的高度]*2*num
        ans += (ali[i + 1].y - ali[i].y) * 2 * love[1].segNum;
        pre = love[1].len;//每次都要更新上一次总区间覆盖的长度
    }

    std::cout << ans;

    return 0;
}