扫描线学习笔记

待补

#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
#define ls root << 1
#define rs root << 1 | 1

using namespace std;
const int _ = 1e5 + 7;

// rectangle
struct Rectangle {
    int x, y1, y2, k;
} R[_ << 1];
// Segment
struct Segment {
    int len = 0, cnt = 0;
} T[_ << 4];

int n, c[_], raw[_], val[_], Y[_], NoY = 0;

bool cmp(Rectangle A, Rectangle B) {
    if (A.x == B.x)
        return rand() % 2; //lol
    return A.x < B.x;
}

void Push_Up(int root, int l, int r);
void Change(int root, int l, int r, int L, int R, int val);
int Queue(int root, int l, int r, int L, int R);

signed main() {
    srand(time(0));
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        R[i * 2 - 1] = (Rectangle){x1, y1, y2, 1};
        R[i * 2] = (Rectangle){x2, y1, y2, -1};
        Y[i * 2 - 1] = y1;
        Y[i * 2] = y2;
    }
    sort(R + 1, R + 2 * n + 1, cmp);
    sort(Y + 1, Y + 2 * n + 1);
    int ans = 0, NoY = unique(Y + 1, Y + 2 * n + 1) - Y - 1;

    for (int i = 1; i < 2 * n /*最后一边 k 是 -1 不需要统计*/; i++) {
        // 所有 x 相等的情况只会记入最后一次，即如果 R[i].x == R[i + 1].x 则 R[i + 1].x - R[i].x == 0.
        Change(1, 1, NoY - 1, R[i].y1, R[i].y2, R[i].k);
        ans = ans + (T[1].len * (R[i + 1].x - R[i].x));
    }
    cout << ans << '\n';
    return 0;
}   

void Push_Up(int root, int l, int r) {
    if (T[root].cnt > 0) {
        T[root].len = Y[r + 1] - Y[l];
    } else {
        T[root].len = T[ls].len + T[rs].len;
    }
}
// Y 是离散数组，在 Y 内，每个出现的 Y 值都有出现且递增排序。
void Change(int root, int l, int r, int L, int R, int val) {
    if (Y[r + 1] <= L || R <= Y[l]) return ;
    if (L <= Y[l] && Y[r + 1] <= R) {
        T[root].cnt += val;
        Push_Up(root, l, r);
        return ;
    }
    int mid = l + r >> 1;
    Change(ls, l, mid, L, R, val);
    Change(rs, mid + 1, r, L, R, val);
    Push_Up(root, l, r);
}
int Queue(int root, int l, int r, int L, int R) {
    // lol
    return 0ll;
}