python/TangDou/AcWing/SegmentTree/HDU1828.md

HDU 1828 Picture

题目大意

求所有矩形组成的不规则图形的 边长总和 是多少。

扫描线扫描周长

扫描线扫描周长比扫描面积要麻烦一些,需要解决的问题有两个

• 如何统计每条竖线(也就是 平行于y轴的线段的长度)
• 如何统计每条横线(也就是 平行于x轴的线段的长度)

如图

1、统计每条竖线

我们发现每次扫描线扫描后投影到根节点的总长度与上次扫描所投影的总长度的绝对值之差就是本次扫描所多出的边长。

注：如果不是很理解，就尝试自己是从左到右的扫描线，模拟走一下就明白了

2、统计每条横线

解决这个问题的方法有两种

• ① 与解决第一种方法一样，将扫描线从下至上扫一遍，得到每次增加的水平长度即可。 但是这种方法复杂度要高一点，代码也稍微有点冗长。【不推荐，B格不够高】

• ② 我们发现水平线段的长度就是本次扫描线的x坐标与下一条扫描线的x坐标之差。 关键在于我们要求出本次扫描线与下一条扫描线有多少个水平线段。 我们可以发现水平线段的个数与本次扫描线的 裸露 的断点有关。 因此我们需要用数组lc,rc记录区间的左端点或者右端点是否 裸露。 再用数组c记录区间有几个水平线段:

整体思想和求面积相似。对比于面积，用线段树 多维护三个信息:

• c :该区间上线段端点个数
• lc:该区间左端点是否被覆盖
• rc:该区间右端点是否被覆盖

注：为啥这样做有用呢？你想啊，如果一个区间，它有左右两个子区间，现在左区间报告自己的右端点被覆盖了，右区间报告自己的左端点被覆盖了，是不是就是左右区间之间没有缝隙，也就是连接到一起了？那原来简单的[1,2],[3,4]原来是4个端点，现在就只剩下4-2=2个了。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
typedef long long LL;

struct ScanLine {
    int y1, y2, x, mark;
    const bool operator<(const ScanLine &t) const {
        // 按x由小到大排序，对应扫描线从左到右。如果x坐标一样的两条竖线，入边=1在前，出边=-1在后
        // 如果出现了两条x坐标相同的扫描线，也就是两矩形相邻
        // 那么需要先扫入边再扫出边，否则就会多算这条边
        // 这个对面积并无影响但对周长并有影响
        // hack 数据：2 0 0 4 4 4 0 8 4 输出应为：24

        // 加上这句判断，答案正确：24
        // 去掉这句判断，答案错误：32,也就是把中间那两条重合的边都加上了边长，加了两遍。
        // 解决办法：先算入边再算出边即可
        if (x == t.x) return mark > t.mark;
        return x < t.x;
    }

} line[N];

// 线段树结构体
struct Node {
    int l, r;    // 边界
    int cnt;     // 被整体覆盖了几次
    int len;     // 被覆盖的长度
    int c;       // 区间中总共有多少裸露的断点
    bool lc, rc; // 左端点是否被覆盖,右端点是否被覆盖

} tr[N << 2];

int b[N]; // 离散化数组

void pushup(int u) {
    if (tr[u].cnt) {                                          // 如果u被完整覆盖
        tr[u].len = b[tr[u].r + 1] - b[tr[u].l];              // 利用离散化数组，计算在线段树中节点，映射回原始数据的R,L,计算两者之间的差值，就是y轴上的坐标差，也就是矩形的竖边边长
                                                              // 因为u管辖的范围被整体覆盖，所以，被覆盖的长度需要换算成真实的长度
        tr[u].c = 2;                                          // 区间中裸露的断点有2个
        tr[u].lc = tr[u].rc = true;                           // 左端点被覆盖,右端点被覆盖
    } else {                                                  // 如果没有被完整覆盖
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;      // 被覆盖的长度=左儿子被覆盖的长度+右儿子被覆盖的长度
        tr[u].c = tr[u << 1].c + tr[u << 1 | 1].c;            // 区间中总共有多少条竖线=左儿子有多少条竖线+右儿子有多少条竖线
        tr[u].lc = tr[u << 1].lc;                             // 如果左儿子左端点被覆盖，那么自己的左端点也肯定被覆盖
        tr[u].rc = tr[u << 1 | 1].rc;                         // 如果右儿子右端点被覆盖，那么自己的右端点也肯定被覆盖
        if (tr[u << 1 | 1].lc && tr[u << 1].rc) tr[u].c -= 2; // 如果做儿子右端点和右儿子左端点都被覆盖，那么中间就是连续的一段，所以要 -= 1
    }
}

// 区间修改，没有使用懒标记
void modify(int u, int l, int r, int v) {
    if (l <= tr[u].l && r >= tr[u].r) {
        tr[u].cnt += v;
        pushup(u);
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid) modify(u << 1, l, r, v);
    if (r > mid) modify(u << 1 | 1, l, r, v);
    pushup(u);
}

// 构建线段树
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("HDU1828.in", "r", stdin);
#endif
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    while (cin >> n) {
        memset(tr, 0, sizeof tr); // 多组测试数据，注意清空数组

        int x1, y1, x2, y2;
        for (int i = 1; i <= n; i++) {
            cin >> x1 >> y1 >> x2 >> y2;
            line[i * 2 - 1] = {y1, y2, x1, 1}; // 入边
            line[i * 2] = {y1, y2, x2, -1};    // 出边
            b[i * 2 - 1] = y1, b[i * 2] = y2;  // 将y坐标记录到离散化数组中
        }
        // n个矩形，2*n条竖边
        n <<= 1;

        sort(line + 1, line + n + 1); // 将扫描线按x由小到大排序，竖着的扫描线

        sort(b + 1, b + n + 1); // 将离散化数组排序，去重
        int tot = unique(b + 1, b + 1 + n) - b - 1;

        build(1, 1, tot - 1); // 构建线段树

        LL res = 0;   // 结果值
        int last = 0; // 前一条扫描线中有效的竖线长度和

        for (int i = 1; i < n; i++) {                                // 前n-1条竖边，最后一条单独处理
            int L = lower_bound(b + 1, b + tot + 1, line[i].y1) - b; // 通过二分查找出原始值y1在离散化数组中的位置
            int R = lower_bound(b + 1, b + tot + 1, line[i].y2) - b;
            modify(1, L, R - 1, line[i].mark); // 对于映射后的区间[L,R)=[L,R-1]进行修改,++--

            // 横线和
            // tr[1].c: 横边的有效个数,一般情况下，一条竖边是两个点，如果有粘在一起的，就需要特殊计算，比如-2
            // line[i + 1].x - line[i].x:竖着的扫描线，横坐标的差，就是个矩形的宽度
            res += (LL)tr[1].c * (line[i + 1].x - line[i].x);

            // 竖线和
            // 每次的边长和，与上次的边长和差的绝对值，为竖着的有效长度
            res += (LL)abs(tr[1].len - last);

            // 记录下来本次的竖着的有效长度,以便后续使用
            last = tr[1].len;
        }
        // 单独处理最后一条边,对于前面每一条，都是line[i+1].x-line[i].x,而最后一条没有，但它确实是存在长度，需要单独计算
        res += line[n].y2 - line[n].y1;
        // 输出结果
        printf("%lld\n", res);
    }
    return 0;
}

Hack数据解释：

2 
0 0 4 4 
4 0 8 4

如图，两个矩形共享了同一条边EB，此时，需要在排序时保证x坐标一致时，入边在前，出边在后，才能保证计算正确，否则就会造成重复计算，得到错误答案 32。