Luogu P5490 【模板】扫描线

题目描述

https://www.luogu.com.cn/problem/P5490

简要题意：给定 $n$ 个矩形，求这些矩形的并集覆盖的总面积，注意这里面积是连续而不是离散的

$n\le 10^5$

Solution

我们考虑扫描线，那么我们线段树只需要维护有哪些位置被覆盖了，注意到我们覆盖和撤销的位置一样，且每次只需要求全局的覆盖情况，所以我们实际上并不需要下穿标记

另外离散化之后我们令点 $i$ 表示的区间为 $[b_i,b_{i+1})$，时间复杂度 $O(n\log n)$

#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 100010
#define ll long long
using namespace std;

int n, xl[maxn], xr[maxn], yl[maxn], yr[maxn];

int b[maxn * 2], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = yl[i], b[i + n] = yr[i];
    sort(b + 1, b + 2 * n + 1); cnt = unique(b + 1, b + 2 * n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) {
        yl[i] = lower_bound(b + 1, b + cnt + 1, yl[i]) - b;
        yr[i] = lower_bound(b + 1, b + cnt + 1, yr[i]) - b;
    }
}

struct node {
    int k, l, r, v;
    friend bool operator < (const node &u, const node &v) { return u.k < v.k; }
} a[maxn * 2];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int v, cnt;
} T[maxn * 8];
inline void maintain(int i, int l, int r) { T[i].v = T[i].cnt ? b[r + 1] - b[l] : T[lc].v + T[rc].v; }

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ; 
    if (L <= l && r <= R) {
        T[i].cnt += v;
        T[i].v = T[i].cnt ? b[r + 1] - b[l] : (l == r ? 0 : T[lc].v + T[rc].v);
        return ;
    } int m = l + r >> 1;
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i, l, r); 
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> xl[i] >> yl[i] >> xr[i] >> yr[i]; init_hash();
    for (int i = 1; i <= n; ++i) a[i] = { xl[i], yl[i], yr[i], 1 }, a[i + n] = { xr[i], yl[i], yr[i], -1 };
    sort(a + 1, a + 2 * n + 1); ll ans = 0; 
    for (int i = 1; i < 2 * n; ++i) {
        update(1, 1, cnt - 1, a[i].l, a[i].r - 1, a[i].v);
        ans += 1ll * T[1].v * (a[i + 1].k - a[i].k); 
    } cout << ans << "\n";
    return 0; 
}