4012 컨벤션 센터

Problem

$n$개의 구간 $[L_i, R_i]$가 주어진다. ( $n \leq 200\ 000$ )

겹치지 않는 구간들을 최대한 많이 골라, 번호의 집합이 사전순으로 최소인 것을 찾아라.

Algorithm

각 구간에 대해 $2^i$ 번째 후의 구간 번호를 담는 Sparse Table을 만든다. $1$번 구간부터 차례대로 보면서 삽입했을 때 나뉜 두 구간에서 각각 최적해가 존재하는 지를 Sparse Table을 이용해서 확인하고, 존재한다면 답에 추가하는 과정을 반복하면 된다.

시간 복잡도는 $O(nlogn)$.

Idea

사전순으로 최소인 최적해를 찾기 위해, $1$번부터 순서대로 보면서 해당 구간을 포함하는 최적해가 존재하는 지 여부를 확인할 수 있으면 된다.

단순하게 매번 확인하는 것은 적어도 $O(n^2)$ 이 소요될 것으로 보이므로, 최적해에 대해 조금 더 관찰을 해 볼 필요가 있다.

가능한 여러가지 최적해들을 생각해보자. 구간 개수가 최대라는 조건 때문에, 서로 다른 최적해에서 선택된 구간들의 분포는 대충 비슷비슷할 것이다. 만약 그렇지 않다면, 적당한 다른 구간들을 선택해서 사이에 구간을 하나 더 끼워넣을 수 있는 형태로 변형이 가능할 것이라는 느낌이 든다.

또 우리는 그리디 알고리즘으로 다음의 특수한 두 가지 최적해를 찾을 수 있다는 것을 알고 있다.

  • $k$ 번째로 선택된 구간의 $R$ 값이 각 $k$에 대해 최소인 해
  • $k$ 번째로 선택된 구간의 $L$ 값이 각 $k$에 대해 최대인 해

대충 생각해서, “모든 구간이 가능한 한 왼쪽에 있는 해”와 “모든 구간이 가능한 한 오른쪽에 있는 해” 라고 생각해도 좋다. 각각 “왼쪽 해”와 “오른쪽 해”로 부르기로 하자.

그러면 이제 $ k $번째로 선택 가능한 구간의 후보가 어떤 범위로 주어질 것 같다는 생각이 든다. 약간의 시행착오를 거쳐, 다음 사실을 얻을 수 있다.

“왼쪽 해”에서 $k$ 번째 구간의 $R$값을 $R_k$, “오른쪽 해”에서 $k$번째 구간의 $L$값을 $L_k$라고 하면,

  • $L_1 \leq R_1 < L_2 \leq R_2 <\ …\ < L_K \leq R_k$
  • 어떤 구간 $[l, r]$이 $k$번째로 선택 가능한 후보일 필요충분조건은 $[l, r]$이 위의 값들 중 오직 $L_k$와 $R_k$ 만을 포함하는 것이다.

증명은 Case Work로 가능하다. 대부분 그 반대가 성립한다고 가정했을 때 “왼쪽 해” 또는 “오른쪽 해”의 성질에 모순이거나, 최적이라는 것에서 모순이 발생하는 식으로 증명된다.

이 성질을 이용하면 각 구간이 몇 번째로 선택될 수 있는 지에 대한 정보는 lower_bound, std::set, 세그먼트 트리 등을 이용해서 $O(log n)$ 에 찾을 수 있다.

이제 각 구간이 들어갈 수 있는 위치가 고정되었으므로, 문제 상황이 훨씬 간단해졌다. 구간의 위치가 고정되었기 때문에, 각 구간을 선택했을 때마다 인접한 다른 구간 사이에 추가적으로 몇 개의 구간을 더 선택해야 하는 지를 알 수 있다.

인접한 구간의 정보를 찾는 것은 std::set을 통해 $O(log n)$에 가능하다. 그러면 이제, 주어진 시간 범위 $[T_l, T_r]$ 에서 $k$개의 겹치지 않는 구간을 선택할 수 있는 지를 빠르게 확인할 수 있으면 문제가 해결되는데, 이는 Sparse Table을 이용하여 $O(log k)$ 시간에 가능하다.

Code

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
74
75
76
77
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int M = 2e5 + 10;
const int INF = 1e9 + 10;

int n, c, ans, I[M], C[M], X[M], Y[M], L[M], R[M], P[20][M];
pint A[M];
set<pint> S;
vector<int> V;
vector<pint> T;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> X[i] >> Y[i]; A[i] = { X[i], Y[i] };
    }
    stable_sort(A + 1, A + 1 + n, [&](pint a, pint b) {
        return a.vb == b.vb ? a.va < b.va : a.vb < b.vb;
        });
    for (int i = 1, s = 0; i <= n; i++) {
        if (A[i].va <= s) continue;
        s = A[i].vb; ++ans; R[ans] = A[i].vb;
    }
    c = ans;
    stable_sort(A + 1, A + 1 + n, [&](pint a, pint b) {
        return a.va == b.va ? a.vb > b.vb : a.va > b.va;
        });
    for (int i = 1, s = INF; i <= n; i++) {
        if (A[i].vb >= s) continue;
        s = A[i].va; L[c] = A[i].va; c--;
    }
    stable_sort(A + 1, A + 1 + n, [&](pint a, pint b) {
        return a.vb == b.vb ? a.va < b.va : a.vb < b.vb;
        });
    for (int i = 1; i <= n; i++) P[0][i] = i;
    for (int i = 1; i < 20; i++) {
        int p = 1;
        for (int j = 1; j <= n; j++) {
            while (p <= n && A[j].va > A[P[i - 1][p]].vb) {
                P[i][p++] = P[i - 1][j];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        I[i] = lower_bound(A + 1, A + 1 + n, pint(X[i], Y[i]), [&](pint a, pint b) {
            return a.vb == b.vb ? a.va < b.va : a.vb < b.vb;
            }) - A;
    }
    for (int i = 1; i <= ans; i++) {
        T.emplace_back(L[i], i); T.emplace_back(R[i], i);
    }
    A[n + 1].va = INF; I[n + 1] = n + 1;
    S.insert({ 0, 0 }); S.insert({ ans + 1, n + 1 });
    for (int i = 1; i <= n; i++) {
        auto it1 = lower_bound(T.begin(), T.end(), pint(X[i], 0));
        auto it2 = upper_bound(T.begin(), T.end(), pint(Y[i], INF));
        if (it2 - it1 != 2 || prev(it2)->vb != it1->vb) continue;
        int k = it1->vb;
        if (C[k]) continue;
        auto it = S.lower_bound({ k, 0 });
        int x = I[i], y = I[prev(it)->vb], l = k - prev(it)->va - 1, r = it->va - k - 1;
        for (int j = 19; j >= 0; j--) {
            if (r >> j & 1) x = P[j][P[1][x]];
            if (l >> j & 1) y = P[j][P[1][y]];
        }
        if (A[x].vb >= A[I[it->vb]].va || A[y].vb >= X[i]) continue;
        S.insert({ k, i });
        C[k] = i; V.push_back(i);
    }
    cout << ans << '\n';
    for (int x : V) cout << x << ' ';
}