BOJ 2995 생일

BOJ 2995 생일

[분류 : 세그먼트 트리]

 

[풀이]

  [좌표평면] 구간의 왼쪽들을 x축으로, 구간의 오른쪽들을 y축으로 생각해보자. 좌표평면으로 옮긴 두 구간을 비교할 땐 두 점을 비교하는 걸로 동치로 볼 수 있다. 둘 중에 한 점이 x축이 작고 y축이 크면 다른 한 점(구간)을 포함한다라고 볼 수 있다.

 

< 빨간점이 포함하는 점(구간)은 초록색 점들이다. >

 

  [정렬] 세그먼트 트리 갱신해야하기 때문에 정렬을 수행한다. 나는 x축을 비오름차순으로, y축을 비내림차순으로 접근했다. 이렇게 접근하면 방문하고 있는 x좌표는 지금까지 방문한 좌표들보다 무조건 작거나 같으므로 구간을 포함할 수 있는 가능성을 열어두게끔 한다. 반대로 y좌표는 같거나 작아야하는 좌표들 중 가장 큰 값을 가져와야하므로 구간 최대를 가져오기 위해 세그먼트 트리를 사용한다.

 

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
using seg_data = pair<int, int>;
const int MAX_N = 1e5;
struct _d { int l, r; } pos[MAX_N];
bool operator<(const _d& a, const _d& b) {
    return a.l != b.l ? a.l < b.l : a.r > b.r;
}
struct seg_tree {
    vector<seg_data> v_tree;
    size_t n;
    seg_tree(int nsize) {
        n = nsize;
        v_tree.resize((n + 1) * 2, {0, -1});
    }
    seg_data query(int l, int r) {
        seg_data res = {0, -1};
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, v_tree[l++]);
            if (r % 2 == 0) res = max(res, v_tree[r--]);
        }
        return res;
    }

    void update(int idx, seg_data d) {
        for (v_tree[idx += n] = d; idx > 1; idx >>= 1)
            v_tree[idx >> 1] = max(v_tree[idx], v_tree[idx ^ 1]);
    }
};
int main() {
    int N, M, y[MAX_N], trace[MAX_N], i, maxi = 0, idx;
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d%d", &pos[i].l, &pos[i].r);
        y[i] = pos[i].r;
    }
    sort(pos, pos + N);
    sort(y, y + N);
    M = unique(y, y + N) - y;
    seg_tree st(M);
    for (i = N - 1; i >= 0; i--) {
        int ypos = lower_bound(y, y + M, pos[i].r) - y;
        seg_data d = st.query(0, ypos);
        trace[i] = d.second;
        st.update(ypos, {d.first + 1, i});
        if (maxi < d.first + 1) {
            maxi = d.first + 1;
            idx = i;
        }
    }
    printf("%d\n", maxi);
    do {
        printf("%d %d\n", pos[idx].l, pos[idx].r);
        idx = trace[idx];
    } while (idx != -1);
    return 0;
}