2106번: 흑염소 감금하기

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

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 25e4;
int n, res, idx[MXN * 2], sz;
struct line {
    int l, r, x, c;
}e[MXN * 2];
struct st {
    int l, r, c, s, maxi;
}tree[MXN * 8];
void update(int h, int l, int r, int gl, int gr, int c) {
    if (gr < l || r < gl) return;
    if (gl <= l&&r <= gr) {
        if (!tree[h].maxi) tree[h].l = l, tree[h].r = r, tree[h].c = 1;
        tree[h].maxi += c;
        tree[h].s += c;
        return;
    }
    update(h * 2 + 1, l, (l + r) / 2, gl, gr, c);
    update(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, c);
    tree[h].maxi = 0;
    if (tree[h * 2 + 1].maxi>tree[h * 2 + 2].maxi) {
        tree[h].l = tree[h * 2 + 1].l;
        tree[h].r = tree[h * 2 + 1].r;
        tree[h].c = tree[h * 2 + 1].c;
        tree[h].maxi = tree[h * 2 + 1].maxi;
    }
    else if (tree[h * 2 + 1].maxi < tree[h * 2 + 2].maxi) {
        tree[h].l = tree[h * 2 + 2].l;
        tree[h].r = tree[h * 2 + 2].r;
        tree[h].c = tree[h * 2 + 2].c;
        tree[h].maxi = tree[h * 2 + 2].maxi;
    }
    else if (tree[h * 2 + 1].maxi) {
        tree[h].l = tree[h * 2 + 1].l;
        tree[h].r = tree[h * 2 + 2].r;
        tree[h].maxi = tree[h * 2 + 1].maxi;
        tree[h].c = tree[h * 2 + 1].c + tree[h * 2 + 2].c - (tree[h * 2 + 1].r == tree[h * 2 + 2].l - 1);
    }
    if (!tree[h].maxi&&tree[h].s) tree[h].l = l, tree[h].r = r, tree[h].c = 1;
    tree[h].maxi += tree[h].s;
}
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);
        e[i] = { y1,y2,x1,1 };
        e[i + n] = { y1,y2,x2,-1 };
        idx[i] = y1;
        idx[i + n] = y2;
    }
    sort(e, e + 2 * n, [](line i, line j) {return i.x < j.x; });
    sort(idx, idx + 2 * n);
    sz = unique(idx, idx + 2 * n) - idx;
    int maxi = 0, t;
    for (int i = 0; i < 2 * n; i++) {
        int l = lower_bound(idx, idx + sz, e[i].l) - idx,
            r = lower_bound(idx, idx + sz, e[i].r) - idx - 1;
        update(0, 0, sz - 2, l, r, e[i].c);
        if (tree[0].maxi > maxi) {
            maxi = tree[0].maxi;
            res = t = 0;
        }
        if (tree[0].maxi == maxi&&tree[0].c > t) res += tree[0].c - t;
        t = tree[0].maxi == maxi ? tree[0].c : 0;
    }
    printf("%d %d", maxi, res);
    return 0;
}