低质量扫描线模板

模板题

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define D(x) cout << #x << " : " << x << endl
using namespace std;
constexpr int N = 1e5 + 10;
using ll = long long;

int n;
struct rec {
    int x1, y1, x2, y2;
} a[N];
int buffer[N * 2];
struct line {
    int y, x1, x2, op;
} b[N * 2];

int l[N * 8], r[N * 8], len[N * 8], tag[N * 8];
void build(int u, int L, int R) {
    l[u] = L, r[u] = R;
    len[u] = tag[u] = 0;
    if (L < R) {
        int mid = (L + R) / 2;
        build(u * 2, L, mid);
        build(u * 2 + 1, mid + 1, R);
    }
}

void upd(int u) {
    if (tag[u] > 0)
        len[u] = buffer[r[u] + 1] - buffer[l[u]];
    else
        len[u] = l[u] == r[u] ? 0 : len[u * 2] + len[u * 2 + 1];
}

void add(int u, int L, int R, int d) {
    if (L == l[u] && R == r[u]) {
        tag[u] += d, upd(u);
        return;
    }
    int mid = (l[u] + r[u]) / 2;
    if (R <= mid)
        add(u * 2, L, R, d);
    else if (L > mid)
        add(u * 2 + 1, L, R, d);
    else
        add(u * 2, L, mid, d), add(u * 2 + 1, mid + 1, R, d);
    upd(u);
}

signed main() {
    cin >> n;
    rep(i, 1, n) scanf("%d %d %d %d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
    rep(i, 1, n) buffer[i * 2 - 1] = a[i].x1, buffer[i * 2] = a[i].x2;
    sort(buffer + 1, buffer + n * 2 + 1);
    rep(i, 1, n) a[i].x1 = lower_bound(buffer + 1, buffer + n * 2 + 1, a[i].x1) - buffer,
                 a[i].x2 = lower_bound(buffer + 1, buffer + n * 2 + 1, a[i].x2) - buffer;
    rep(i, 1, n) b[i * 2 - 1] = (line){a[i].y1, a[i].x1, a[i].x2, 1},
                           b[i * 2] = (line){a[i].y2, a[i].x1, a[i].x2, -1};
    sort(b + 1, b + 1 + n * 2, [](line x, line y) { return x.y < y.y; });
    build(1, 1, n * 2 - 1);
    ll s = 0;
    rep(i, 1, n * 2) {
        if (i > 1) {
            s += (ll)(b[i].y - b[i - 1].y) * len[1];
        }
        add(1, b[i].x1, b[i].x2 - 1, b[i].op);
    }
    cout << s << endl;
    return 0;
}

注意upd