7626번: 직사각형

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


$O(n\lg n)$

http://codedoc.tistory.com/421

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MXN = 2e5;
int n, idx[MXN * 2], e, lt[MXN * 8], ct[MXN * 8];
ll res;
struct st {
    int x, y1, y2, t;
}line[MXN * 2];
void update(int h, int l, int r, int gl, int gr, int x) {
    if (r < gl || gr < l) return;
    if (gl <= l && r <= gr) ct[h] += x;
    else {
        update(h * 2 + 1, l, (l + r) / 2, gl, gr, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
    }
    if (ct[h]) lt[h] = idx[r + 1] - idx[l];
    else lt[h] = l^r ? lt[h * 2 + 1] + lt[h * 2 + 2] : 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x1, x2, y1, y2; i < n; i++) {
        scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
        line[i] = { x1,y1,y2,1 };
        line[i + n] = { x2,y1,y2,-1 };
        idx[i] = y1;
        idx[i + n] = y2;
    }
    sort(line, line + 2 * n, [](st i, st j) {return i.x < j.x; });
    sort(idx, idx + 2 * n);
    e = unique(idx, idx + 2 * n) - idx;
    for (int i = 0; i < 2 * n; i++) {
        if (i) res += (ll)lt[0] * (line[i].x - line[i - 1].x);
        update(0, 0, e - 1, lower_bound(idx, idx + e, line[i].y1) - idx,
            lower_bound(idx, idx + e, line[i].y2) - idx - 1, line[i].t);
    }
    printf("%lld", res);
    return 0;
}