1666번: 최대 증가 직사각형 집합

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


$O(n\lg n)$

시작점과 끝점의 y 성분을 가지고 최댓값을 리턴하는 세그먼트 트리를 만들 것이다.
시작점과 끝점을 x를 기준으로 오름차순 정렬한 다음 앞에서부터 본다. 같은 x 값이면 시작점이 끝점보다 앞서야 한다.
i) 시작점
세그먼트 트리에서 현재 점의 y 좌표보다 작은 구간에 대해 최댓값을 구한다.
해당 값 + 1은 현재 직사각형을 포함하고 현재 점보다 왼쪽 아래에 있는 직사각형들을 포함한 집합 L의 최대 크기가 된다.
이를 따로 저장해놓는다.
ii) 끝점
앞서 시작점을 스위핑하면서 구한 최댓값+1을 세그먼트 트리에서 현재 점 y 좌표에 갱신해준다.

답은 저장해놓은 L의 최대 크기가 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, c[MXN], tree[MXN * 4], y[MXN], res;
struct st {
    int x, y, t, idx;
}p[MXN * 2];
void update(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    tree[h] = max(tree[h], x);
    if (l^r) {
        update(h * 2 + 1, l, (l + r) / 2, g, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
    }
}
int query(int h, int l, int r, int g) {
    if (g < l) return 0;
    if (r <= g) return tree[h];
    return max(query(h * 2 + 1, l, (l + r) / 2, g), query(h * 2 + 2, (l + r) / 2 + 1, r, g));
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &p[i].x, &p[i].y, &p[i + n].x, &p[i + n].y);
        p[i].idx = p[i + n].idx = i;
        p[i].t = 1;
        y[i] = p[i + n].y;
    }
    sort(p, p + 2 * n, [](st i, st j) {return i.x<j.x || i.x == j.x&&i.t>j.t; });
    sort(y, y + n);
    for (int i = 0; i < 2 * n; i++) {
        int lb = lower_bound(y, y + n, p[i].y) - y;
        if (p[i].t) res = max(res, c[p[i].idx] = query(0, 0, n - 1, lb - 1) + 1);
        else update(0, 0, n - 1, lb, c[p[i].idx]);
    }
    printf("%d", res);
    return 0;
}