백준 1666번: 최대 증가 직사각형 집합 [C++]

작성일 | In
플래티넘 2 플래티넘 2

문제

최대 증가 직사각형 집합

풀이

기본적인 아이디어는 직사각형의 시작점을 기준으로 왼쪽에서 오른쪽으로 스위핑하면서 최대 증가 직사각형 집합을 구한 뒤 끝점을 기준으로 업데이트 해 주는 것입니다.

세그먼트 트리에 끝점을 기준으로 업데이트 되어있으므로 현재 직사각형의 시작점의 $y$보다 작은 범위에서 최댓값을 찾아 $1$을 더하면 현재 직사각형까지의 최대 증가 직사각형 집합의 크기가 됩니다.

그러나 다음 직사각형의 시작점의 $x$ 좌표가 현재 직사각형의 끝점보다 작을 수 있으므로 우선순위 큐를 이용해 지연된 갱신을 하면 됩니다.

시간 복잡도 $\mathcal{O}(N\log N)$ 정도에 해결할 수 있습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;

struct Rectangle {
    auto operator<=>(const Rectangle& rect) const = default;
    pair<int, int> s, e;
};

struct SegmentTree {
    int n;
    vector<int> t;

    SegmentTree(int n): n(n), t(n << 1) {}

    void maximize(int i, int v) {
        i += n;
        for (t[i] = max(t[i], v); i > 1; i >>= 1)
            t[i >> 1] = max(t[i], t[i ^ 1]);
    }

    int getRangeMax(int l, int r) {
        int ret = 0;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1)
                ret = max(ret, t[l++]);
            if (~r & 1)
                ret = max(ret, t[r--]);
        }

        return ret;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<Rectangle> rects(N);
    for (auto& [s, e] : rects) {
        cin >> s.first >> s.second >> e.first >> e.second;
    }
    ranges::sort(rects);

    SegmentTree segTree(100100);
    MinHeap<pair<pair<int, int>, int>> pq;

    for (const auto& rect : rects) {
        while (not pq.empty() and pq.top().first.first < rect.s.first) {
            const auto [e, lis] = pq.top();
            segTree.maximize(e.second, lis);
            pq.pop();
        }

        int lis = segTree.getRangeMax(0, max(0, rect.s.second - 1)) + 1;
        pq.emplace(rect.e, lis);
    }

    while (not pq.empty()) {
        const auto [e, lis] = pq.top();
        segTree.maximize(e.second, lis);
        pq.pop();
    }

    cout << segTree.getRangeMax(0, 100000);
    return 0;
}

백준 1666번: 최대 증가 직사각형 집합 [C++]