3392번: 화성 지도

https://www.acmicpc.net/problem/3392


$O(n\lg L)$

plane sweeping
http://codedoc.tistory.com/421

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e4, MXL = 3e4;
int n, lt[MXL * 4], ct[MXL * 4], res;
struct st {
    int x, y1, y2, s;
}l[MXN * 2];
void update(int h, int l, int r, int gl, int gr, int s) {
    if (r < gl || gr < l) return;
    if (gl <= l && r <= gr) ct[h] += s;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, s);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, s);
    }
    lt[h] = !ct[h] ? l^r ? lt[h * 2 + 1] + lt[h * 2 + 2] : 0 : r - l + 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x1, y1, x2, y2; i < n; i++) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        l[i] = { x1,y1,y2 - 1,1 };
        l[i + n] = { x2,y1,y2 - 1,-1 };
    }
    sort(l, l + 2 * n, [](st i, st j) {return i.x < j.x; });
    for (int i = 0; i < 2 * n; i++) {
        if (i) res += lt[0] * (l[i].x - l[i - 1].x);
        update(0, 0, MXL - 1, l[i].y1, l[i].y2, l[i].s);
    }
    printf("%d", res);
    return 0;
}