此博客为补档博客,只做简单讲解。

对于一个经典问题,求矩形面积的并。

我们考虑把每一个矩形拆分为一个在 X 轴上的一条入线段和一条出线段。具体地,对于一个矩形,若只看其 X 坐标,则该矩形只贡献其中的一条线段。

即尝试维护一个形如以下的结构体的线段:

struct Line {
    int x, y1, y2, type;
};

其中 x 表示这个线段在 X 轴上的坐标,y1 y2 为这条线段在 Y 轴上覆盖的区域,而 type 用于判断入线段还是出线段。

那么我们考虑将其拆分后,用线段树维护 Y 轴上的覆盖长度即可。

具体操作如下:

  • 将所有线段按照 X 坐标进行排序,从小到大遍历所有线段
  • 将线段的 y1 y2 覆盖区间加入线段树中,若某一个 X 坐标的所有线段都被统计完,就计算其面积。

线段树主要维护区间覆盖问题,但是针对这一题,若线段树上的每一个节点只表示线段的端点,那么比较难维护,因为会出现点被覆盖,但线段未被覆盖的情况。

所以我们考虑换一种方式维护,线段树上的每一个节点表示线段上的节点及其与后一个节点之间的线段的覆盖情况。形象地讲,就是我们从维护 $[l,r]$ 到维护 $[l,r)$。

而且这道题目的区间覆盖不需要下传懒标记,因为对于每一个线段如果被覆盖了,那么答案是唯一的,且若未被覆盖,则答案就是子树的答案,而子树的答案一定会在修改的时候更新,而不依赖于父亲节点的答案。

/*
 * Author: chhokmah
 * Date: 2020-08-17 21:42:52
 */

#include <bits/stdc++.h>

#define y2 LZMAKIOI

using namespace std;

template <typename T>
void read(T& x) {
    x = 0;
    int c = 0, f = 0;
    for (; !isdigit(c); c = getchar()) f |= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c & 15);
    x = f ? -x : x;
}

const int N = 2e5 + 5;

struct Line {
    int x, y1, y2, type;

    bool operator<(const Line& rhs) const {
        return x < rhs.x;
    }
} s[N << 1];

int n, dcnt, m;
int disc[N << 1];
long long ans = 0;

struct Node {
    int sum;
    int cnt;  //cover precisely
} seg[N << 4];

void pushup(int p, int l, int r) {
    if (seg[p].cnt > 0)
        seg[p].sum = disc[r + 1] - disc[l];
    else if (seg[p << 1].cnt > 0 && seg[p << 1 | 1].cnt > 0)
        seg[p].sum = disc[r + 1] - disc[l];
    else
        seg[p].sum = seg[p << 1].sum + seg[p << 1 | 1].sum;
}

void modify(int p, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
        seg[p].cnt += v;
        pushup(p, l, r);
        return;
    }
    int mid = l + r >> 1;
    if (ql <= mid) modify(p << 1, l, mid, ql, qr, v);
    if (qr > mid) modify(p << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(p, l, r);
}

int main() {
    read(n);
    for (int i = 1; i <= n; i++) {
        int x1, x2, y1, y2;
        read(x1), read(y1), read(x2), read(y2);
        s[++m] = (Line){x1, y1, y2, 1};
        s[++m] = (Line){x2, y1, y2, -1};
        disc[++dcnt] = y1;
        disc[++dcnt] = y2;
    }
    sort(s + 1, s + 1 + m);
    sort(disc + 1, disc + 1 + dcnt);
    dcnt = unique(disc + 1, disc + 1 + dcnt) - disc - 1;
    s[m + 1].x = s[m].x;
    for (int i = 1; i <= m; i++) {
        s[i].y1 = lower_bound(disc + 1, disc + 1 + dcnt, s[i].y1) - disc;
        s[i].y2 = lower_bound(disc + 1, disc + 1 + dcnt, s[i].y2) - disc;
        modify(1, 1, dcnt, s[i].y1, s[i].y2 - 1, s[i].type);
        if (s[i].x != s[i + 1].x) ans += 1ll * seg[1].sum * (s[i + 1].x - s[i].x);
    }
    printf("%lld\n", ans);
    return 0;
}
最后修改:2020 年 08 月 25 日 10 : 20 PM
如果觉得我的文章对你有用,请随意赞赏