2026 한국정보올림피아드 2차 대회 문제 풀이

작성일 | In

서론

2026년 7월 18일에 개최된 2026 한국정보올림피아드 2차대회 문제 풀이입니다.

  1번 2번 3번 4번
초등부 거리두기 주사위 탑 쌓기 간식 분배 게임
중등부 주사위 탑 쌓기 간식 분배 게임 수열 연산
고등부 간식 분배 극솟값 제거 곡예 공장

네트워크 플로우는 KOI 역사상 처음, 이분 매칭을 포함하더라도 2007년 이후로 두 번째로 등장했습니다. IOI Syllabus에는 $O(E\cdot \vert F\vert)$ Ford-Fulkerson을 이용한 최대 유량의 계산과 max-flow min-cut theorem이 2025년(link)부터 추가되었습니다. 2021년 중등부에 접미사 배열이 나온 것을 보면 KOI가 꼭 IOI Syllabus 안에 있는 것만 출제하는 것 같진 않지만…

고등부 2번과 3번은 만점을 받는 방법이 여러 개 있습니다. 모두 재미있고 교육적으로도 유익한 내용이므로 공부하는 것을 추천합니다.

고등부 4번을 제외한 다른 문제는 만점 풀이와 관련 있는 서브태스크만, 고등부 4번은 모든 서브태스크를 설명합니다. PC로 보는 경우 오른쪽 사이드바에서 원하는 문제로 이동할 수 있습니다.

초등부 1번. 거리두기

모든 $1 \le i < N$에 대해 $B_{i+1} - B_i = K$인 경우만 고려해도 충분합니다. $B_{i+1} - B_i > K$인 $i$가 존재한다면, $B_{i+1}, B_{i+2}, \cdots, B_N$을 각각 1씩 감소해도 $B_1$을 유지하면서 올바른 해를 만들 수 있기 때문입니다. 따라서 $B_1$의 값을 $x$로 만들 수 있는지 확인하는 건, 모든 $1 \le i \le N$에 대해 $B_i = x + (i-1)K \le A_i$인지 확인하면 됩니다.

어떤 정수 $x$가 주어졌을 때 $O(N)$ 시간에 $x$가 답이 될 수 있는지 확인할 수 있으므로, 전체 프로그램의 시간 복잡도는 $x$의 탐색 범위에 따라 결정됩니다. 항상 $B_1 \le A_1 \le \max A_i$가 성립하므로 $x$는 최대 $\max A_i \le 100$까지만 확인하면 됩니다. 반대로, $A_N = 1$이면 $B_N = x + (N-1)K = 1$이 되어야 하고, 따라서 $1 - (N-1)K \le x$ 범위는 탐색해야 한다는 것을 알 수 있습니다. 넉넉하게 $-NK \le x \le \max A_i$ 범위를 탐색한다고 하더라도 시간 안에 문제를 해결할 수 있습니다.

$O(N)$ 시간에도 문제를 해결할 수 있습니다. 모든 $1 \le i \le N$에 대해 $B_i = x+(i-1)K \le A_i$가 성립하는 $x$의 최댓값을 찾으면 되는데, 식을 정리하면 $x \le A_i - (i-1)K$ 가 되고, 이는 $\min_{1 \le i \le N} \lbrace A_i - (i-1)K \rbrace$를 구하는 것과 같습니다. 따라서 $O(N)$ 시간에 $x$로 가능한 최댓값을 구한 뒤, 다시 $O(N)$ 시간에 수열 $B$를 복원하여 문제를 해결할 수도 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int N, K, A[111];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<=N; i++) cin >> A[i];
    int mn = 1e9;
    for(int i=1; i<=N; i++) mn = min(mn, A[i] - K * (i-1));
    for(int i=1; i<=N; i++) cout << mn + (i - 1) * K << " ";
}

초등부 2번/중등부 1번. 주사위 탑 쌓기

1과 6으로 탑을 만드는 문제, 2와 5로 탑을 만드는 문제, 3과 4로 탑을 만드는 문제, 이렇게 3개의 독립된 문제로 나눠서 생각해도 됩니다. $i$가 나온 주사위가 $x$개, $7-i$가 나온 주사위가 $y$개 있을 때 탑의 개수를 최소화하는 상황을 생각해 봅시다. 일반성을 잃지 않고 $x \ge y$ 인 상황만 생각할 것입니다.

$x = y$ 이면 x - y - x - y - ... - x - y 형태의 탑 1개로 주사위를 모두 쌓을 수 있습니다. 마찬가지로 $x = y + 1$ 일 때도 x - y - x - y - ... - x 형태의 탑 1개로 주사위를 모두 쌓을 수 있습니다. 여기에서 관찰할 수 있는 것은, 한 개의 탑으로는 $i$와 $7-i$가 나온 주사위를 같은 개수로 없애거나, 한쪽 주사위를 하나 더 가져갈 수 있다는 점입니다.

따라서 $x - y = 0$이면 1개의 탑으로, $x - y = d > 0$ 이면 $d$개의 탑으로 모든 주사위를 쌓을 수 있습니다. $i$와 $7-i$가 나온 주사위가 모두 0개일 때를 조심해서 구현해야 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int N, C[7], R;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1,t; i<=N; i++) cin >> t, C[t]++;
    for(int i=1; i<=3; i++) if(C[i] > 0 || C[7-i] > 0) R += max(1, abs(C[i] - C[7-i]));
    cout << R;
}

초등부 3번/중등부 2번/고등부 1번. 간식 분배

$N$명의 학생과 $N$개의 간식이 있으므로, 모든 학생이 간식을 가져가기 위해서는 각 학생이 한 개의 간식만 가져가야 합니다. 따라서 현재 남은 간식 중 $i$번 학생이 좋아하는 간식의 수를 $Deg(i)$라고 정의했을 때, $Deg(i) = 1$인 학생을 방에 들여보내는 그리디 전략을 생각해 볼 수 있습니다. 그리고 해가 존재하는 경우, 이 그리디 전략이 항상 해를 찾음을 증명할 수 있습니다.

위 관찰을 했다면 만점 풀이는 위상 정렬과 비슷한 방식으로 어렵지 않게 작성할 수 있습니다. 각 학생이 좋아하는 간식 목록(A[i])과, 각 간식을 좋아하는 학생 목록(B[i])를 저장한 뒤, $Deg(i) = 1$인 학생 $i$가 나타날 때마다 큐에 넣는 방식으로 구현하면 $O(N+\sum C_i)$ 시간에 문제를 해결할 수 있습니다.

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
#include <bits/stdc++.h>
using namespace std;

int N, Deg[202020], Use[202020];
vector<int> A[202020], B[202020], R;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> Deg[i]; A[i].resize(Deg[i]);
        for(auto &j : A[i]) cin >> j, B[j].push_back(i);
    }

    queue<int> Q;
    for(int i=1; i<=N; i++) if(Deg[i] == 1) Q.push(i);
    while(!Q.empty()){
        int v = Q.front(); Q.pop(); R.push_back(v);
        if(Deg[v] != 1){ cout << -1; return 0; }
        for(auto i : A[v]) if(!Use[i]) for(auto j : B[i]) if(--Deg[j] == 1) Q.push(j);
        for(auto i : A[v]) Use[i] = 1;
    }
    if(R.size() < N) cout << -1;
    else for(auto i : R) cout << i << " ";
}

초등부 4번/중등부 3번. 게임

Subtask 4. $k_1 = k_2 = \cdots = k_Q$ (21점)

고정된 $k$에 대해 문제를 해결하는 방법을 먼저 생각해 봅시다.

현재 정점 $v$에 연결되어 있는 간선 중, Alice가 승리할 수 있다고 알려진 정점으로 가는 간선이 $k$개 이상이라면 $v$에서도 Alice가 승리할 수 있습니다. 따라서 다음과 같은 방식을 생각해 볼 수 있습니다.

  1. 출구가 있는 정점을 win position으로 표시
  2. 어떤 정점 $v$에서 win position인 정점으로 가는 간선이 $k$개 이상이면 $v$도 win position으로 표시
  3. 더 이상 win position에 추가되는 정점이 없을 때까지 반복

위상 정렬과 비슷하게, win position 정점이 추가될 때마다 큐에 넣는 식으로 구현하면 $O(N+M)$ 시간에 각 정점이 win position인지 판별할 수 있습니다. 따라서 $k$가 고정되어 있는 경우 $O(N+M+Q)$ 시간에 답을 구할 수 있습니다.

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N, M, Q, A[202020];
vector<pair<int,int>> G[202020];
ll S[202020], K[202020];
ll cnt[202020], chk[202020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> Q;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=M; i++){
        int u, v, w; cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    for(int i=1; i<=Q; i++) cin >> S[i] >> K[i];
    assert(count(K+1, K+Q+1, K[1]) == Q); // subtask 4

    queue<int> que; ll k = K[1];
    for(int i=1; i<=N; i++) if(A[i]) que.push(i), chk[i] = 1;
    while(!que.empty()){
        int v = que.front(); que.pop();
        for(auto [i,w] : G[v]){
            if(chk[i]) continue;
            if((cnt[i] += w) >= k) que.push(i), chk[i] = 1;
        }
    }

    for(int i=1; i<=Q; i++) cout << (chk[S[i]] ? "YES" : "NO") << "\n";
}

Subtask 7. 추가 제약 조건 없음 (100점)

$(s, k)$에서 Alice가 승리한다면 $(s, k-1)$에서도 Alice가 승리합니다. 따라서 각 정점 $s$에 대해, $s$에서 Alice가 승리하는 최대 $k$를 찾으면 쿼리를 상수 시간에 처리할 수 있습니다. 그러한 $k$를 $D(s)$라고 합시다. $A_i = 1$이면 $D(i) = \infty$입니다. 각 쿼리 $(s, k)$의 답은 단순히 $D(s) \ge k$인지 확인하는 것으로 구할 수 있습니다.

$D(\ast)$의 값이 큰 정점부터 차례대로 처리할 것입니다.

$D(v) = c$로 확정되었다고 합시다. 이는 모든 $k \le c$에 대해 $v$에서 Alice가 승리할 수 있음을 의미합니다. $v$와 인접하면서 아직 $D(i)$의 값이 확정되지 않은 $i$가 있고, $v$와 $i$를 잇는 간선이 $w$개 있다고 합시다.

기존에 $i$가 확보한 win position으로 가는 간선을 이용해 $k \le D(i)$ 범위에서 승리를 보장할 수 있었다면, $w$개의 간선이 추가되면서 그 값은 최대 $D(i) + w$까지 증가할 수 있어 보입니다. 하지만 새로 추가된 간선은 정점 $v$로 가는 간선이기 때문에, $v$에서 Alice가 이길 수 있는 $k \le c$ 에서만 사용할 수 있습니다. 따라서 $v$에서 $i$로 가는 간선이 $w$개 있다면, $D(i) \leftarrow \max(D(i), \min(c, D(i)+w))$로 갱신할 수 있습니다.

위 과정은 다익스트라 알고리즘과 유사한 방식으로 계산할 수 있습니다. max heap을 이용해 $D(\ast)$의 값이 가장 큰 정점 $v$를 뽑은 뒤 $D(v)$를 확정시키고, $v$에서 확정되지 않은 정점 $i$로 가는 간선을 이용해 정보를 갱신하면 $O((N+M) \log M)$ 시간에 $D(\ast)$를 모두 계산할 수 있습니다.

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N, M, Q, A[202020]; ll D[202020];
vector<pair<int,int>> G[202020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> Q;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=M; i++){
        int u, v, w; cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }

    priority_queue<pair<ll,ll>> pq;
    for(int i=1; i<=N; i++) if(A[i]) pq.emplace(D[i]=1e18, i);
    while(!pq.empty()){
        auto [c,v] = pq.top(); pq.pop();
        if(c == D[v]) for(auto [i,w] : G[v]) if(c > D[i]) pq.emplace(D[i]=min(c, D[i]+w), i);
    }

    for(int q=1; q<=Q; q++){
        ll s, k; cin >> s >> k;
        cout << (D[s] >= k ? "YES" : "NO") << "\n";
    }
}

중등부 4번. 수열 연산

Subtask 3. $M = N$ (12점)

1번 연산(교환 연산)만 사용해서 $A$와 $B$를 같게 만들어야 합니다.

어떤 수 $x$가 $B$에서 등장하는 위치를 $P(x)$라고 정의합시다. 만약 $i < j$ 이면서 $A_i > A_j$라면, $A_i$와 $A_j$의 상대적인 순서는 바뀔 수 없습니다. 따라서 $i < j, A_i > A_j$ 이면 $P(A_i) < P(A_j)$가 성립해야 하고, 이 조건이 필요충분조건입니다.

위 조건이 성립할 때 실제로 $A$를 $B$로 변환하는 것은, $A$의 왼쪽에 있는 원소부터 차례대로 보면서 삽입 정렬을 수행하면 됩니다. 조건을 확인하는 것, 그리고 삽입 정렬을 수행하는 것 모두 $O(N^2)$ 시간에 가능합니다.

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
#include <bits/stdc++.h>
using namespace std;

int N, M, A[3030], B[3030], Pos[3030];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=M; i++) cin >> B[i], Pos[B[i]] = i;

    bool flag = true;
    for(int i=1; i<=N; i++) for(int j=i+1; j<=N; j++) if(A[i] > A[j]) flag &= Pos[A[i]] < Pos[A[j]];
    if(!flag){cout << "NO"; return 0; }

    vector<int> R;
    for(int i=2; i<=N; i++){
        for(int x=i; x>1; x--){
            if(Pos[A[x-1]] > Pos[A[x]]) R.push_back(x-1), swap(A[x-1], A[x]);
            else break;
        }
    }

    cout << "YES\n" << R.size() << "\n";
    for(auto i : R) cout << 1 << " " << i << "\n";
}

Subtask 5. $M = N-1$ (25점)

$B$에 포함되지 않은 원소가 하나 존재합니다. 2번 연산(합치기 연산)을 이용해 그 원소를 제거한 뒤 Subtask 3의 문제를 해결하면 됩니다.

$B$에 포함되지 않은 원소를 $A_p = x$라고 합시다. $x$ 를 없애기 위해서는 $x$와 $x$보다 작은 원소가 인접하도록 만든 뒤 2번 연산을 적용해야 합니다. $x$보다 작은 원소가 왼쪽에 있는 경우와 오른쪽에 있는 경우를 나눠서 생각해 봅시다.

$A_p$보다 오른쪽에 있는 $A_p$보다 작은 원소 중 가장 왼쪽에 있는 원소를 $A_q = y < x$ 라고 합시다. 이러한 $q$가 존재한다면, 정의에 의해 $A_{p+1}, A_{p+2}, \cdots, A_{q-1}$은 모두 $x, y$보다 큽니다. 따라서 1번 연산을 $q-p-1$번 이용해 $x$를 $A_{q-1}$로 옮긴 뒤, 2번 연산을 적용하면 $x$를 없앨 수 있습니다.

$A_p$보다 오른쪽에 $A_p$보다 작은 원소가 없는 경우, 즉 $A_p$가 suffix min인 경우만 남았습니다. 이 경우에는 $A_p$보다 작은 원소를 왼쪽에서 찾아야 합니다. $A_p$보다 왼쪽에 있으면서 $P(\ast)$가 가장 큰 수를 $A_r = z$라고 합시다. 만약 $z < x$ 라면 $A_1, A_2, \cdots, A_{p-1}$을 $P(\ast)$ 오름차순으로 정렬한 뒤, 2번 연산을 적용하면 $x$를 없앨 수 있습니다.

$z > x$ 지만 $A_p$ 왼쪽에 $A_p$보다 작은 수 $A_s = w$가 있을 수 있습니다. 하지만 $A_s$와 $A_p$ 사이에 $A_p$보다 큰 수가 있으므로 $x$를 왼쪽으로 옮길 수 없고, $w$를 $A_p$ 바로 왼쪽으로 옮기면 나중에 $P(\ast)$ 오름차순이 되도록 남은 수를 정렬할 수 없습니다. 따라서 $z > x$ 면 $A = B$가 되도록 만들 수 없습니다.

따라서 $A = B$로 만들기 위해 필요한 조건은 다음과 같습니다.

  1. $i < j$, $A_i > A_j$이고 $A_i,A_j \in B$ 이면 $P(A_i) < P(A_j)$
  2. $A_i = x \not \in B$ 이면서 $A_i$가 suffix min이면, $A_i$보다 왼쪽에 있는 $P(\ast)$가 가장 큰 원소 $A_r = z$에 대해 $z < x$.

Subtask 8. 추가 제약 조건 없음 (100점)

Subtask 5와 같은 방법으로 해결할 수 있습니다. 여기에서는 구현 방법에 대해 조금 더 자세하게 설명합니다.

먼저 $B$에 없는 원소 중 $A$에서 suffix min이 아닌 원소를 모두 없앱니다. $A$를 뒤에서부터 차례대로 보면서 suffix min이 아닌 원소 $A_i = x$를 만날 때마다, $x$보다 더 작은 원소를 만날 때까지 1번 연산을 이용해 뒤로 보낸 뒤, 2번 연산으로 $x$를 없앨 수 있습니다. 각 원소가 최대 $O(N)$번 뒤로 이동할 수 있으므로, 이 단계의 시간 복잡도는 $O(N^2)$입니다.

이제, $A$에 남은 원소를 앞에서부터 차례대로 보면서, 현재 원소가 $B$에 포함된 원소라면 삽입 정렬을 이용해 $P(\ast)$ 오름차순이 되도록 위치를 옮깁니다. 만약 현재 원소가 $B$에 포함되지 않았다면, 이미 바로 왼쪽에 $P(\ast)$가 가장 큰 원소가 있는 상태이므로 바로 2번 연산을 적용하면 됩니다. 이 단계 또한 $O(N^2)$ 시간에 모두 끝낼 수 있습니다.

시간 복잡도가 $O(N^2)$라는 것은 쉽게 알 수 있지만, 1번 연산과 2번 연산의 시행 횟수가 $N^2$번 이하인지는 다시 확인하는 게 좋습니다.

  1. 교환 연산은 항상 수열의 inversion을 늘리는 방향으로만 수행할 수 있습니다. 길이가 $N$인 수열에서 가능한 inversion의 최댓값은 ${N\choose 2} = N(N-1)/2$이므로, 교환 연산은 최대 $N(N-1)/2$번 수행할 수 있습니다.
  2. 합치기 연산을 수행하면 수열의 길이가 1 감소합니다. 길이가 $N$인 수열에서 원소를 $N-M$개 삭제해야 하므로, 합치기 연산은 정확히 $N-M$번 수행해야 합니다.

$N \ge 1$이면 항상 $N(N-1)/2 + N-M \le N^2$이 성립합니다.

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
#include <bits/stdc++.h>
using namespace std;

vector<int> Simulate(vector<int> a, vector<pair<int,int>> ops){
    for(auto [op,i] : ops){
        if(op != 1 && op != 2) return {};
        if(i < 1 || i + 1 > a.size()) return {};
        i--;
        if(op == 1) assert(a[i] < a[i+1]), swap(a[i], a[i+1]);
        if(op == 2) a[i] = min(a[i], a[i+1]), a.erase(a.begin()+i+1);
    }
    return a;
}

vector<pair<int,int>> Solve(vector<int> a, vector<int> b){
    vector<pair<int,int>> res;

    int n = a.size(), m = b.size();
    vector<int> pb(n+1, -1);
    for(int i=0; i<m; i++) pb[b[i]] = i;

    auto op_swap = [&](int i){
        res.emplace_back(1, i+1);
        swap(a[i], a[i+1]);
    };
    auto op_del = [&](int i){
        res.emplace_back(2, i+1);
        a[i] = min(a[i], a[i+1]);
        a.erase(a.begin()+i+1);
    };

    for(int i=n-1, mn=n+1; i>=0; i--){
        if(a[i] < mn){ mn = a[i]; continue; }
        if(pb[a[i]] != -1) continue;
        int x = i;
        while(x + 1 < n && a[x] < a[x+1]) op_swap(x), x++;
        op_del(x);
    }

    for(int i=0; i<a.size(); i++){
        if(pb[a[i]] == -1){
            if(i > 0 && a[i-1] < a[i]) op_del(i-1), i--;
            else return {};
            continue;
        }
        for(int x=i; x>0; x--){
            if(pb[a[x-1]] < pb[a[x]]) break;
            if(a[x-1] < a[x]) op_swap(x-1);
            else return {};
        }
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<int> A(N), B(M);
    for(auto &i : A) cin >> i;
    for(auto &i : B) cin >> i;
    auto R = Solve(A, B);
    if(Simulate(A, R) != B){ cout << "NO"; return 0; }
    cout << "YES\n" << R.size() << "\n";
    for(auto [op,i] : R) cout << op << " " << i << "\n";
}

고등부 2번. 극솟값 제거

Subtask 2. $l = 1, r = N$ (17점)

$l = 1, r = N$인 문제의 풀이를 먼저 생각해 봅시다. $A_{i-1} > A_i < A_{i+1}$인 $A_i$를 모두 한 번에 삭제하는 연산은, 1번 정점과 $N$번 정점이 아닌 카르테시안 트리의 리프 정점을 모두 삭제하는 것이라고 생각할 수 있습니다. 카르테시안 트리에서 $i$번 정점의 높이를 $H_i$라고 정의합시다(리프 정점이면 $H_i = 1$). 연산을 $t$번 연달아 수행하면, 1번 정점과 $N$번 정점의 조상을 제외하고 $H_i \le t$인 정점들만 모두 사라집니다.

$A_i$보다 오른쪽에 있으면서 $A_i$보다 큰 원소 중 가장 왼쪽에 있는 원소의 위치를 $R(i)$라고 합시다. 다시 말해, $R(i) = \min_{i < j, A_i < A_j} j$입니다. 마찬가지로 $L(i) = \max_{i>j, A_i<A_j} j$도 정의합시다. 카르테시안 트리에서 1번 정점의 조상은 $1, R(1), R^2(1), \cdots$이고, $N$번 정점의 조상은 $N, L(N), L^2(N), \cdots$입니다. 따라서 $l = 1, r = N$ 일 때 제거되지 않는 정점은 다음과 같습니다. (단, $m$은 최댓값의 위치)

  1. $H_i > t$인 정점
  2. $1, R(1), R^2(1), \cdots, m$ 중 $H_i \le t$인 정점 (prefix max)
  3. $N, L(N), L^2(N), \cdots, m$ 중 $H_i \le t$인 정점 (suffix max)
  4. $H_m \le t$이면 (2)와 (3)에서 두 번 세었으므로 답을 1 줄여야 함

$H$, $L$, $R$ 모두 monotone stack을 이용하면 $O(N)$ 시간에 구할 수 있습니다. 이후 (1), (2), (3) 모두 누적 합 배열을 이용하면 $O(N)$ 시간 전처리 후 매 쿼리마다 $O(1)$ 시간에 계산할 수 있습니다. 따라서 $O(N+Q)$ 시간에 $l = 1, r = N$인 문제를 해결할 수 있습니다.

(2)와 (3) 대신 카르테시안 트리에서 1번 정점과 $N$번 정점을 잇는 경로 위에 있는 정점을 본다고 생각해도 $l = 1, r = 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
#include <bits/stdc++.h>
using namespace std;

int N, Q, A[202020], Pos[202020], L[202020], R[202020], H[202020];
int S1[202020], S2[202020], S3[202020];

void Init(){
    vector<int> stk;
    for(int i=1; i<=N; i++){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        if(!stk.empty()) L[i] = stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for(int i=N; i>=1; i--){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        if(!stk.empty()) R[i] = stk.back();
        stk.push_back(i);
    }
    auto par = [](int x) -> int {
        if(!L[x] || !R[x]) return L[x] + R[x];
        return A[L[x]] < A[R[x]] ? L[x] : R[x];
    };
    fill(H+1, H+N+1, 1);
    for(int i=1; i<=N; i++){
        int x = Pos[i], p = par(x);
        if(p) H[p] = max(H[p], H[x] + 1);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) Pos[A[i]] = i;
    Init();

    int mx = max_element(A+1, A+N+1) - A;
    for(int i=1; i<=N; i++) S1[H[i]] += 1;
    for(int i=1; i; i=R[i]) S2[H[i]] += 1;
    for(int i=N; i; i=L[i]) S3[H[i]] += 1;
    for(int i=1; i<=N; i++) S1[i] += S1[i-1], S2[i] += S2[i-1], S3[i] += S3[i-1];

    auto get_sum = [](int *a, int l, int r) -> int {
        return l <= r ? a[r] - (l ? a[l-1] : 0) : 0;
    };

    for(int q=1; q<=Q; q++){
        int l, r, t; cin >> l >> r >> t;
        assert(l == 1 && r == N);
        cout << get_sum(S1, t+1, N) + get_sum(S2, 1, t) + get_sum(S3, 1, t) - (H[mx] <= t) << "\n";
    }
}

만점 풀이 - Persistent segment tree

구간 쿼리가 주어지더라도 똑같습니다. 쿼리 $(l, r, t)$가 주어졌을 때, 연산으로 인해 없어지지 않는 정점은 다음과 같습니다. (단, $m$은 $[l, r]$ 구간에서 최댓값의 위치)

  1. $l \le i \le r$ 이면서 $H_i > t$인 정점
  2. $l, R(l), R^2(l), \cdots, m$ 중 $H_i \le t$인 정점 (구간의 prefix max)
  3. $r, L(r), L^2(r), \cdots, m$ 중 $H_i \le t$인 정점 (구간의 suffix max)
  4. $H_m \le t$이면 (2)와 (3)에서 두 번 세었으므로 답을 1 줄여야 함

$l$과 $r$이 고정되지 않아서 Subtask 2와 같이 누적 합 배열을 이용할 수 없습니다.

(1)은 Persistent segment tree로 해결할 수 전형적인 형태이므로, $O(N \log N)$ 전처리 후에 매 쿼리마다 $O(\log N)$ 시간에 계산할 수 있습니다.

(2)에서 $i \leftarrow R(i)$ 간선을 만들면 포레스트가 나오므로, $l, R(l), R^2(l), \cdots, m$에서 $H_i \le t$인 정점의 수를 구하는 것은 트리의 경로에서 $H_i \le t$인 정점의 수를 구하는 것이라고 생각할 수 있습니다. 따라서 (2) 또한 PST를 이용하면 $O(N \log N)$ 전처리 후에 매 쿼리마다 $O(\log N)$ 시간에 계산할 수 있습니다. (3)도 같은 방법으로 계산할 수 있습니다.

따라서 전체 문제를 $O((N+Q) \log N)$ 시간에 해결할 수 있습니다. (2)에서 $LCA(m, l) = m$이라는 것을 이용하면 구현을 조금 더 편하게 할 수 있습니다.

만약 Subtask 2에서 prefix max와 suffix max 대신 $l$과 $r$을 잇는 경로로 접근했다면, Subtask 7에서는 경로 위의 정점이 $[l, r]$ 구간을 벗어나게 되어서 2D PST가 필요해 집니다.

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 18;

struct node{
    int l, r, v;
    node() : l(0), r(0), v(0) {}
};

struct persistent_segment_tree{
    vector<node> T;
    vector<int> root;
    persistent_segment_tree() : T(2), root(1, 1) {}
    void _update(int prv, int now, int s, int e, int x, int v){
        if(s == e){ T[now].v = T[prv].v + v; return; }
        int m = (s + e) / 2;
        if(x <= m){
            T[now].l = T.size(); T.emplace_back();
            T[now].r = T[prv].r;
            _update(T[prv].l, T[now].l, s, m, x, v);
        }
        else{
            T[now].l = T[prv].l;
            T[now].r = T.size(); T.emplace_back();
            _update(T[prv].r, T[now].r, m+1, e, x, v);
        }
        T[now].v = T[T[now].l].v + T[T[now].r].v;
    }
    int _query(int prv, int now, int s, int e, int l, int r){
        if(r < s || e < l || prv == now) return 0;
        if(l <= s && e <= r) return T[now].v - T[prv].v;
        int m = (s + e) / 2;
        return _query(T[prv].l, T[now].l, s, m, l, r) + _query(T[prv].r, T[now].r, m+1, e, l, r);
    }
    void clone_and_add(int prv, int now, int s, int e, int x){
        assert(prv < root.size() && root[prv] != 0);
        if(now >= root.size()) root.resize(now+1);
        root[now] = T.size(); T.emplace_back();
        _update(root[prv], root[now], s, e, x, 1);
    }
    int value_count(int prv, int now, int s, int e, int l, int r){
        assert(max(prv,now) < root.size() && root[prv] != 0 && root[now] != 0);
        return _query(root[prv], root[now], s, e, l, r);
    }
};

int N, Q, A[202020], Pos[202020], L[202020], R[202020], H[202020];
persistent_segment_tree Seq, Le, Ri;
pair<int,int> T[SZ<<1];

void Init(){
    vector<int> stk;
    for(int i=1; i<=N; i++){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        if(!stk.empty()) L[i] = stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for(int i=N; i>=1; i--){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        if(!stk.empty()) R[i] = stk.back();
        stk.push_back(i);
    }
    auto par = [](int x) -> int {
        if(!L[x] || !R[x]) return L[x] + R[x];
        return A[L[x]] < A[R[x]] ? L[x] : R[x];
    };
    fill(H+1, H+N+1, 1);
    for(int i=1; i<=N; i++){
        int x = Pos[i], p = par(x);
        if(p) H[p] = max(H[p], H[x] + 1);
    }

    for(int i=1; i<=N; i++) T[i|SZ] = {A[i], i};
    for(int i=SZ-1; i; i--) T[i] = max(T[i<<1], T[i<<1|1]);
}

int GetMax(int l, int r){
    pair<int,int> res(-1, -1);
    for(l|=SZ, r|=SZ; l<=r; l>>=1, r>>=1){
        if(l & 1) res = max(res, T[l++]);
        if(~r & 1) res = max(res, T[r--]);
    }
    return res.second;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) Pos[A[i]] = i;
    Init();

    for(int i=1; i<=N; i++) Seq.clone_and_add(i-1, i, 1, N, H[i]);
    for(int i=N; i>=1; i--){
        int x = Pos[i];
        Le.clone_and_add(L[x], x, 1, N, H[x]);
        Ri.clone_and_add(R[x], x, 1, N, H[x]);
    }

    for(int q=1; q<=Q; q++){
        int l, r, t; cin >> l >> r >> t;
        int res = 0, mx = GetMax(l, r);
        res += Seq.value_count(l-1, r, 1, N, t+1, N);
        res += Ri.value_count(R[mx], l, 1, N, 1, t);
        res += Le.value_count(L[mx], r, 1, N, 1, t);
        res -= H[mx] <= t;
        cout << res << "\n";
    }
}

만점 풀이 - Sparse table

  1. $l \le i \le r$ 이면서 $H_i > t$인 정점
  2. $l, R(l), R^2(l), \cdots, m$ 중 $H_i \le t$인 정점 (구간의 prefix max)
  3. $r, L(r), L^2(r), \cdots, m$ 중 $H_i \le t$인 정점 (구간의 suffix max)
  4. $H_m \le t$이면 (2)와 (3)에서 두 번 세었으므로 답을 1 줄여야 함

쿼리를 오프라인으로 처리할 수 있다면, 모든 쿼리를 $t$ 내림차순으로 정렬해서 (1)을 단순히 Segment tree나 Fenwick tree만 이용해 처리할 수 있습니다. 또한, (2)에서 $H_l, H_{R(l)}, H_{R^2(l)}, \cdots, H_m$가 증가하는 수열이라는 점을 관찰하면, PST 대신 Sparse table을 이용한 이분 탐색(binary lifting)으로 각 쿼리를 $O(\log N)$에 처리할 수 있습니다. 따라서 PST 를 구현하지 않고도 $O((N+Q) \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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 18;

struct Query{
    int l, r, t, i, res;
};

int N, Q, A[202020], Pos[202020], L[202020], R[202020], H[202020];
int LP[22][202020], RP[22][202020];
vector<Query> V;
pair<int,int> T[SZ<<1];
int F[202020];

void Init(){
    vector<int> stk;
    for(int i=1; i<=N; i++){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        if(!stk.empty()) L[i] = stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for(int i=N; i>=1; i--){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        if(!stk.empty()) R[i] = stk.back();
        stk.push_back(i);
    }
    auto par = [](int x) -> int {
        if(!L[x] || !R[x]) return L[x] + R[x];
        return A[L[x]] < A[R[x]] ? L[x] : R[x];
    };
    fill(H+1, H+N+1, 1);
    for(int i=1; i<=N; i++){
        int x = Pos[i], p = par(x);
        if(p) H[p] = max(H[p], H[x] + 1);
    }

    for(int i=1; i<=N; i++) T[i|SZ] = {A[i], i};
    for(int i=SZ-1; i; i--) T[i] = max(T[i<<1], T[i<<1|1]);
}

int GetMax(int l, int r){
    pair<int,int> res(-1, -1);
    for(l|=SZ, r|=SZ; l<=r; l>>=1, r>>=1){
        if(l & 1) res = max(res, T[l++]);
        if(~r & 1) res = max(res, T[r--]);
    }
    return res.second;
}

void Add(int x, int v){ for(x+=3; x<202020; x+=x&-x) F[x] += v; }
int Sum(int x){ int r = 0; for(x+=3; x; x-=x&-x) r += F[x]; return r; }
int Sum(int l, int r){ return l <= r ? Sum(r) - Sum(l-1) : 0; }

int BinarySearch(int p[22][202020], int v, int m, int t){
    if(H[v] > t) return 0;
    int res = 1;
    for(int i=21; i>=0; i--){
        if(p[i][v] == 0 || A[p[i][v]] > A[m]) continue;
        if(H[p[i][v]] <= t) res += 1 << i, v = p[i][v];
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q; V.resize(Q); Q = 0;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(auto &[l,r,t,i,res] : V) cin >> l >> r >> t, i = ++Q, res = 0;

    for(int i=1; i<=N; i++) Pos[A[i]] = i;
    Init();

    vector<pair<int,int>> U; U.reserve(N);
    for(int i=1; i<=N; i++) U.emplace_back(H[i], i);
    sort(U.begin(), U.end(), greater<>());
    sort(V.begin(), V.end(), [](auto x, auto y){ return x.t > y.t; });
    for(int i=0, j=0; j<Q; j++){
        while(i < N && U[i].first > V[j].t) Add(U[i++].second, 1);
        V[j].res += Sum(V[j].l, V[j].r);
    }

    for(int i=1; i<=N; i++) LP[0][i] = L[i], RP[0][i] = R[i];
    for(int i=1; i<22; i++) for(int j=1; j<=N; j++) LP[i][j] = LP[i-1][LP[i-1][j]], RP[i][j] = RP[i-1][RP[i-1][j]];
    for(auto &[l,r,t,i,res] : V){
        int mx = GetMax(l, r);
        res += BinarySearch(RP, l, mx, t);
        res += BinarySearch(LP, r, mx, t);
        res -= H[mx] <= t;
    }

    sort(V.begin(), V.end(), [](auto x, auto y){ return x.i < y.i; });
    for(auto i : V) cout << i.res << "\n";
}

만점 풀이 - 2D Segment tree

$l = 1, r = N$일 때 $A_i$가 없어지는 시점을 $T(i)$라고 정의합시다. 카르테시안 트리에서 $1$ 또는 $N$의 조상이면 $T(i) = \infty$, 그렇지 않으면 $T(i) = H_i$입니다.

쿼리 $(l, r, t)$에서 $A_i$가 제거될 조건은 $L(i) \ge l, R(i) \le r, T(i) \le t$입니다. 따라서 각 원소 $A_i$를 3차원 좌표 공간 상의 점 $(N-L(i)+1, R(i), T(i))$라고 정의하면, 쿼리 $(l, r, t)$는 $(N-l+1, r, t)$에 dominate 되는 점의 수를 세는 것으로 생각할 수 있습니다.

점과 쿼리를 x좌표 순으로 정렬하면 x좌표를 무시할 수 있게 되므로, 쿼리로 $(y, z)$가 주어지면 $py \le y, pz \le z$인 점 $(py, pz)$의 수를 세는 문제가 됩니다. 2D Segment tree나 2D Fenwick tree를 이용하면 $O((N+Q) \log^2 N)$ 시간에 문제를 해결할 수 있습니다.

사용하는 좌표를 미리 모두 구할 수 있다는 점을 이용하면, 2D Fenwick tree의 공간 복잡도를 $O(N^2)$이 아닌 $O(N \log N)$으로 만들 수 있습니다. 자세한 방법은 아래 코드에서 fenwick_tree와 fenwick_tree_2d 함수의 coord 관련 로직을 확인하시길 바랍니다.

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
#define lb(x) (lower_bound(coord.begin(), coord.end(), x) - coord.begin())
#define ub(x) (upper_bound(coord.begin(), coord.end(), x) - coord.begin())
using namespace std;

struct Point{
    int x, y, z, i; Point() = default;
    Point(int x, int y, int z, int i) : x(x), y(y), z(z), i(i) {}
    bool operator < (const Point &p) const { return tie(x,i) < tie(p.x,p.i); }
};

struct fenwick_tree{
    vector<int> tree;
    vector<int> coord;
    void init(const vector<int> &values){
        coord = values;
        sort(coord.begin(), coord.end());
        coord.erase(unique(coord.begin(), coord.end()), coord.end());
        tree = vector<int>(coord.size()+5);
    }
    void add(int x, int v){
        if(tree.empty()) return;
        for(x=lb(x)+3; x<tree.size(); x+=x&-x) tree[x] += v;
    }
    int get(int x) const {
        if(tree.empty()) return 0;
        int res = 0;
        for(x=ub(x)-1+3; x; x-=x&-x) res += tree[x];
        return res;
    }
};

struct fenwick_tree_2d{
    vector<fenwick_tree> tree;
    vector<int> coord;
    void init(const vector<pair<int,int>> values){
        coord.resize(values.size());
        for(int i=0; i<coord.size(); i++) coord[i] = values[i].first;
        sort(coord.begin(), coord.end());
        coord.erase(unique(coord.begin(), coord.end()), coord.end());
        tree = vector<fenwick_tree>(coord.size()+5);

        tree = vector<fenwick_tree>(coord.size()+5);
        vector<vector<int>> pos(coord.size()+5);
        for(auto [x,y] : values) for(x=lb(x)+3; x<tree.size(); x+=x&-x) pos[x].push_back(y);
        for(int i=0; i<tree.size(); i++) tree[i].init(pos[i]);
    }
    void add(int x, int y, int v){
        if(tree.empty()) return;
        for(x=lb(x)+3; x<tree.size(); x+=x&-x) tree[x].add(y, v);
    }
    int get(int x, int y) const {
        if(tree.empty()) return 0;
        int res = 0;
        for(x=ub(x)-1+3; x; x-=x&-x) res += tree[x].get(y);
        return res;
    }
};

int N, Q, A[202020], Pos[202020], L[202020], R[202020], H[202020], Ans[202020];

void Init(){
    vector<int> stk;
    for(int i=1; i<=N; i++){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        if(!stk.empty()) L[i] = stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for(int i=N; i>=1; i--){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        if(!stk.empty()) R[i] = stk.back();
        stk.push_back(i);
    }
    auto par = [](int x) -> int {
        if(!L[x] || !R[x]) return L[x] + R[x];
        return A[L[x]] < A[R[x]] ? L[x] : R[x];
    };
    fill(H+1, H+N+1, 1);
    for(int i=1; i<=N; i++){
        int x = Pos[i], p = par(x);
        if(p) H[p] = max(H[p], H[x] + 1);
    }
    for(int i=1; i; i=R[i]) H[i] = 1e9;
    for(int i=N; i; i=L[i]) H[i] = 1e9;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) Pos[A[i]] = i;
    Init();

    vector<Point> V; V.reserve(N+Q);
    for(int i=1; i<=N; i++) V.emplace_back(N-L[i]+1, R[i], H[i], -i);
    for(int i=1,l,r,t; i<=Q; i++) cin >> l >> r >> t, V.emplace_back(N-l+1, r, t, i);
    sort(V.begin(), V.end());

    vector<pair<int,int>> C; C.reserve(N);
    for(int i=1; i<=N; i++) C.emplace_back(R[i], H[i]);
    fenwick_tree_2d tree; tree.init(C);

    for(auto [x,y,z,i] : V){
        if(i > 0){
            int l = N - x + 1, r = y;
            Ans[i] = r - l + 1 - tree.get(y, z);
        }
        else tree.add(y, z, 1);
    }
    for(int i=1; i<=Q; i++) cout << Ans[i] << "\n";
}

만점 풀이 - CDQ Divide and Conquer

위에 있는 2D Segment tree 풀이에서 이어집니다. 똑같이 점과 쿼리를 3차원 점으로 만든 뒤, x좌표를 기준으로 정렬해 부등호를 3개에서 2개로 줄입니다.

$\text{DnC}(l,r)$은 $l, l+1, \cdots, r$번째 점/쿼리만 고려했을 때 없어지는 점의 개수를 구하는 함수입니다. 이는 아래와 같이 세 단계로 나눠서 계산할 수 있습니다. (단, $m = \lfloor\frac{l+r}{2}\rfloor$)

  1. $\text{DnC}(l,m)$
  2. $\text{DnC}(m+1,r)$
  3. $[l, m]$ 구간에 속한 점과 $[m+1, r]$ 구간에 속한 쿼리 간의 결과

(1)과 (2)는 단순히 DnC 함수를 재귀 호출하는 것으로 처리할 수 있으므로, (3)만 해결하면 됩니다.

$[l, m]$ 구간에 속한 점을 y좌표 오름차순으로, $[m+1, r]$ 구간에 속한 쿼리를 y좌표 오름차순으로 정렬한 뒤, 투 포인터를 이용하면 부등호를 하나 더 줄여서 1차원 구간 쿼리로 바꿀 수 있습니다. 따라서 Fenwick tree 하나만 이용해 답을 구할 수 있습니다. \text{DnC}(l, r)의 끝부분에서 merge sort와 비슷한 방식으로 구간에 속한 점/쿼리를 y좌표 오름차순으로 정렬하면, std::sort와 같은 정렬 함수를 호출하지 않고 빠르게 x좌표 오름차순으로 정렬된 배열을 y좌표 오름차순으로 정렬되도록 수정할 수 있습니다.

시간 복잡도는 $T(N) = 2T(N/2) + O(N \log N) \in O(N \log^2 N)$입니다.

이런 식으로 분할 정복할 때 왼쪽에 있는 원소들이 오른쪽에 있는 원소에 주는 영향을 계산하는 테크닉을 CDQ Divide and Conquer 라고 부릅니다. CDQ의 어원은 중국의 2008년 IOI 금메달리스트이자 현재 프린스턴대학교 컴퓨터학과 교수인 Chen Danqi 입니다.

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
78
79
80
#include <bits/stdc++.h>
using namespace std;

struct Point{
    int x, y, z, i; Point() = default;
    Point(int x, int y, int z, int i) : x(x), y(y), z(z), i(i) {}
    bool operator < (const Point &p) const { return tie(x,i) < tie(p.x,p.i); }
};

int N, Q, A[202020], Pos[202020], L[202020], R[202020], H[202020], Ans[202020];

void Init(){
    vector<int> stk;
    for(int i=1; i<=N; i++){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        if(!stk.empty()) L[i] = stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for(int i=N; i>=1; i--){
        while(!stk.empty() && A[stk.back()] < A[i]) stk.pop_back();
        if(!stk.empty()) R[i] = stk.back();
        stk.push_back(i);
    }
    auto par = [](int x) -> int {
        if(!L[x] || !R[x]) return L[x] + R[x];
        return A[L[x]] < A[R[x]] ? L[x] : R[x];
    };
    fill(H+1, H+N+1, 1);
    for(int i=1; i<=N; i++){
        int x = Pos[i], p = par(x);
        if(p) H[p] = max(H[p], H[x] + 1);
    }
    for(int i=1; i; i=R[i]) H[i] = 1e9;
    for(int i=N; i; i=L[i]) H[i] = 1e9;
}

int T[202020];
void Add(int x, int v){ for(x+=3; x<202020; x+=x&-x) T[x] += v; }
int Get(int x){ int r = 0; for(x+=3; x; x-=x&-x) r += T[x]; return r; }
void Update(const Point &p, int v){ if(p.i < 0) Add(p.z, v); }
void Query(const Point &p){ if(p.i > 0) Ans[p.i] += Get(p.z); }

void DnC(vector<Point> &v, int l, int r){
    if(l == r) return;
    int m = (l + r) / 2;
    DnC(v, l, m); DnC(v, m+1, r);

    int i = l, j = m + 1;
    vector<Point> md; md.reserve(r-l+1);
    while(i <= m && j <= r){
        if(v[i].y <= v[j].y) Update(v[i], 1), md.push_back(v[i]), i++;
        else Query(v[j]), md.push_back(v[j]), j++;
    }
    while(i <= m) Update(v[i], 1), md.push_back(v[i]), i++;
    while(j <= r) Query(v[j]), md.push_back(v[j]), j++;
    for(int k=l; k<=m; k++) Update(v[k], -1);
    for(int k=l; k<=r; k++) v[k] = md[k-l];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) Pos[A[i]] = i;
    Init();

    vector<Point> V; V.reserve(N+Q);
    for(int i=1; i<=N; i++) V.emplace_back(N-L[i]+1, R[i], H[i], -i);
    for(int i=1,l,r,t; i<=Q; i++) cin >> l >> r >> t, V.emplace_back(N-l+1, r, t, i);
    sort(V.begin(), V.end());
    DnC(V, 0, N+Q-1);

    sort(V.begin(), V.end(), [](auto x, auto y){ return x.i < y.i; });
    for(auto [x,y,z,i] : V){
        if(i < 0) continue;
        int l = N - x + 1, r = y;
        cout << r - l + 1 - Ans[i] << "\n";
    }
}

고등부 3번. 곡예

본격적으로 문제 풀이에 들어가기 전에, 몇 가지 관찰을 먼저 해야 합니다.

Observation 1. 구간을 확장하는 점프만 고려해도 된다.

Alice는 오른쪽으로, Bob은 왼쪽으로 이동할 수 있습니다. 구간을 좁히는 것은 자유롭게 할 수 있으므로, 점프대를 통해 구간을 얼마나 많이 넓힐 수 있는지 구하는 것에 집중해야 합니다. 즉, Alice와 Bob이 각각 $a, b$에 있을 때, 아래 두 가지 형태의 점프만 봐도 충분합니다.

  • $y < a \le x < b$ 인 점프대 $(x, y)$: 구간의 왼쪽 끝점을 확장
  • $a < x \le b < y$ 인 점프대 $(x, y)$: 구간의 오른쪽 끝점을 확장

Observation 2. $[a, b]$에서 최대로 확장할 수 있는 구간 $[L, R]$을 계산해 두면, 쿼리는 $L \le c < d \le R$을 판별하기만 하면 된다.

이 명제가 참이라는 것을 보이기 위해서는 $[a, b]$에서 시작해 도달 가능한 maximal한 구간이 모두 같음을 보여야 하지만, 이 글에서는 증명을 생략합니다.

Observation 3. $[i, i+1]$ 형태의 구간만 고려해도 된다.

$[i, i+1]$에서 시작해 도달 가능한 최대 구간을 $[L_i, R_i+1]$라고 합시다. $[a, b]$에서 시작해 도달 가능한 최대 구간은 $\bigcup_{i=a}^{b-1} [L_i, R_i+1]$과 같고, 이는 $[\min_{i=a}^{b-1} L_i, 1 + \max_{i=1}^{b-1} R_i]$입니다.

Subtask 3. $N \le 3\,000$ (21점)

Alice와 Bob이 각각 $i, i+1$에 있는 상태를 $i$번 상태라고 합시다. 총 $N-1$개의 상태가 있으며, 각 상태에서 한 번의 점프로 갈 수 있는 상태로 간선을 연결하면 정점이 $N-1$개인 방향 그래프를 얻을 수 있습니다.

$i$번 상태에서 Alice가 한 번의 점프로 갈 수 있는 가장 왼쪽 상태를 $L_i$, Bob이 한 번에 점프로 갈 수 있는 가장 오른쪽 상태를 $R_i$(위치는 $R_i+1$)라고 하면, $i$번 정점에서 $L_i, L_i+1, \cdots, R_i$번 정점으로 가는 간선을 만들어야 합니다. 따라서 그래프의 간선은 최대 $O(N^2)$개입니다.

이후 각 정점에서 도달 가능한 정점 번호의 최솟값($S_i$)과 최댓값($E_i$)을 구해야 하는데, 이는 SCC를 하나의 정점으로 압축해서 DAG를 만든 다음, DP를 이용해서 $O(V+E)$ 시간에 계산할 수 있습니다. $V \in O(N), E \in O(N^2)$ 이므로 시간 복잡도는 $O(N^2)$이 됩니다.

이후 쿼리를 처리하는 것은, $L = \min_{i=a}^{b-1} S_i$, $R = 1 + \max_{i=a}^{b-1} E_i$를 계산한 뒤 $L \le c < d \le R$인지 판별하면 됩니다. Sparse table을 이용하면 전처리 $O(N \log N)$ 이후 RMQ를 $O(1)$ 시간에 할 수 있으므로, 전체 시간 복잡도는 $O(N^2 + Q)$입니다.

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
#include <bits/stdc++.h>
using namespace std;

template<typename T, typename O>
struct sparse_table{
    int n; vector<vector<T>> t; O op;
    T f(const T &x, const T &y) const { return op(x, y) ? x : y; }
    sparse_table(vector<T> a) : n(a.size()), t(__lg(n)+1, vector<T>(n)), op() {
        copy(a.begin(), a.end(), t[0].begin());
        for(int i=1; i<t.size(); i++) for(int j=0; j+(1<<i)-1<n; j++) t[i][j] = f(t[i-1][j], t[i-1][j+(1<<(i-1))]);
    }
    T get(int l, int r) const {
        int k = __lg(r-l+1);
        return f(t[k][l], t[k][r-(1<<k)+1]);
    }
};

int N, M, Q, L[202020], R[202020];

int K, C[202020], Min[202020], Max[202020];
vector<int> G[202020], G2[202020], T[202020], V;
void AddEdge(int s, int e){ G[s].push_back(e); G2[e].push_back(s); }
void DFS1(int v){
    C[v] = -1;
    for(auto i : G[v]) if(!C[i]) DFS1(i);
    V.push_back(v);
}
void DFS2(int v, int c){
    C[v] = c;
    for(auto i : G2[v]) if(C[i] == -1) DFS2(i, c);
}
void GetSCC(){
    for(int i=1; i<N; i++) if(!C[i]) DFS1(i);
    reverse(V.begin(), V.end());
    for(auto i : V) if(C[i] == -1) DFS2(i, ++K);

    memset(Min, 0x3f, sizeof Min);
    memset(Max, 0xc0, sizeof Max);
    for(int i=1; i<N; i++) Min[C[i]] = min(Min[C[i]], i);
    for(int i=1; i<N; i++) Max[C[i]] = max(Max[C[i]], i);

    for(int i=1; i<N; i++) for(auto j : G[i]) if(C[i] != C[j]) T[C[i]].push_back(C[j]);
    for(int i=K; i>=1; i--) for(auto j : T[i]) Min[i] = min(Min[i], Min[j]), Max[i] = max(Max[i], Max[j]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    iota(L+1, L+N, 1);
    iota(R+1, R+N, 1);
    for(int i=1; i<=M; i++){
        int x, y; cin >> x >> y;
        if(y < x) L[x] = min(L[x], y);
        if(x < y) R[x-1] = max(R[x-1], y-1);
    }
    for(int i=1; i<N; i++) for(int j=L[i]; j<=R[i]; j++) AddEdge(i, j);
    GetSCC();

    iota(L+1, L+N, 1);
    iota(R+1, R+N, 1);
    for(int i=1; i<N; i++) L[i] = Min[C[i]], R[i] = Max[C[i]];
    sparse_table<int, less<>> LT(vector<int>(L, L+N+1));
    sparse_table<int, greater<>> RT(vector<int>(R, R+N+1));

    cin >> Q;
    for(int q=1; q<=Q; q++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        int l = LT.get(a, b-1), r = RT.get(a, b-1) + 1;
        cout << (l <= c && d <= r ? "YES" : "NO") << "\n";
    }
}

만점 풀이 - SCC, $O(N \log N + Q)$

위 풀이에서 문제가 되는 부분은 그래프의 간선이 $O(N^2)$개라는 것입니다. 간선 개수를 줄이면서 그래프를 온전히 표현할 수 있을까요?

$i$에서 어떤 구간 $[L_i, R_i]$로 가는 간선을 만드는 것이므로, 세그먼트 트리를 생각해 볼 수 있습니다. 리프 정점이 $N-1$개인 세그먼트 트리를 만든 뒤, 부모 정점에서 자식 정점으로 가는 간선을 만듭시다.

이후 $i$에서 구간 $[L_i, R_i]$로 이동할 수 있음을 표현할 때 간선을 $R_i-L_i+1$개 만드는 것 대신, 세그먼트 트리에서 구간 $[L_i, R_i]$를 나타내는 $O(\log N)$개의 정점으로 가는 간선을 만듭니다. 리프 정점 간의 도달 가능성을 그대로 보존하면서, 동시에 매번 만들어지는 간선의 개수를 $O(N)$에서 $O(\log N)$으로 줄일 수 있습니다. 따라서 정점이 $O(N)$개, 간선이 $O(N \log N)$개인 그래프를 만들 수 있습니다. 조금 더 구체적으로는 정점이 최대 $4N$개, 간선이 최대 $2N\lceil \log N \rceil$개인 그래프를 만들 수 있습니다.

$O(N \log N)$ 시간에 SCC를 구하고 $S_i$와 $E_i$를 계산한 뒤 Sparse table을 $O(N \log N)$ 시간에 만들면, 각 쿼리의 답을 상수 시간에 구할 수 있습니다. 전체 시간 복잡도는 $O(N \log N + Q)$입니다.

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
78
#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 18;

template<typename T, typename O>
struct sparse_table{
    int n; vector<vector<T>> t; O op;
    T f(const T &x, const T &y) const { return op(x, y) ? x : y; }
    sparse_table(vector<T> a) : n(a.size()), t(__lg(n)+1, vector<T>(n)), op() {
        copy(a.begin(), a.end(), t[0].begin());
        for(int i=1; i<t.size(); i++) for(int j=0; j+(1<<i)-1<n; j++) t[i][j] = f(t[i-1][j], t[i-1][j+(1<<(i-1))]);
    }
    T get(int l, int r) const {
        int k = __lg(r-l+1);
        return f(t[k][l], t[k][r-(1<<k)+1]);
    }
};

int N, M, Q, L[202020], R[202020];

int K, C[SZ<<1], Min[SZ<<1], Max[SZ<<1];
vector<int> G[SZ<<1], G2[SZ<<1], T[SZ<<1], V;
void AddEdge(int s, int e){ G[s].push_back(e); G2[e].push_back(s); }
void Add(int x, int l, int r){
    for(x|=SZ, l|=SZ, r|=SZ; l<=r; l>>=1, r>>=1){
        if(l & 1) AddEdge(x, l++);
        if(~r & 1) AddEdge(x, r--);
    }
}
void DFS1(int v){
    C[v] = -1;
    for(auto i : G[v]) if(!C[i]) DFS1(i);
    V.push_back(v);
}
void DFS2(int v, int c){
    C[v] = c;
    for(auto i : G2[v]) if(C[i] == -1) DFS2(i, c);
}
void GetSCC(){
    for(int i=1; i<SZ*2; i++) if(!C[i]) DFS1(i);
    reverse(V.begin(), V.end());
    for(auto i : V) if(C[i] == -1) DFS2(i, ++K);
    memset(Min, 0x3f, sizeof Min);
    memset(Max, 0xc0, sizeof Max);
    for(int i=1; i<=N; i++) Min[C[i|SZ]] = min(Min[C[i|SZ]], i);
    for(int i=1; i<=N; i++) Max[C[i|SZ]] = max(Max[C[i|SZ]], i);

    for(int i=1; i<SZ*2; i++) for(auto j : G[i]) if(C[i] != C[j]) T[C[i]].push_back(C[j]);
    for(int i=K; i>=1; i--) for(auto j : T[i]) Min[i] = min(Min[i], Min[j]), Max[i] = max(Max[i], Max[j]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    iota(L+1, L+N+1, 1);
    iota(R+1, R+N+1, 1);
    for(int i=1; i<=M; i++){
        int x, y; cin >> x >> y;
        if(y < x) L[x] = min(L[x], y);
        if(x < y) R[x] = max(R[x], y);
    }
    for(int i=1; i<N; i++) Add(i, L[i], R[i+1]-1); // (i, i+1) -> (L[i], R[i+1])
    for(int i=1; i<SZ; i++) AddEdge(i, i<<1), AddEdge(i, i<<1|1);
    GetSCC();

    iota(L+1, L+N+1, 1);
    iota(R+1, R+N+1, 1);
    for(int i=1; i<N; i++) L[i] = Min[C[i|SZ]], R[i] = Max[C[i|SZ]];
    sparse_table<int, less<>> LT(vector<int>(L, L+N+1));
    sparse_table<int, greater<>> RT(vector<int>(R, R+N+1));

    cin >> Q;
    for(int q=1; q<=Q; q++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        int l = LT.get(a, b-1), r = RT.get(a, b-1) + 1;
        cout << (l <= c && d <= r ? "YES" : "NO") << "\n";
    }
}

만점 풀이 - SCC, $O(N + Q)$

Subtask 3의 풀이에서 문제가 되는 부분은 그래프의 간선이 $O(N^2)$개라는 것입니다. 위에서 본 $O(N \log N)$ 풀이는 그래프의 도달 가능성을 유지하면서 간선의 개수를 줄이는 방법이었습니다. 도달 가능성을 유지하는 것을 포기하면 어떤 일이 생길까요?

우리가 실제로 필요한 정보는 각 정점에서 갈 수 있는 정점 번호의 최솟값과 최댓값이지, 도달 가능한 정점들의 전체 리스트가 필요하지는 않습니다. 정점 $v$에서 아래 두 정점으로 가는 간선만 만든, $N-1$개의 정점과 $2N-2$개의 간선으로 구성된 그래프를 생각해 봅시다.

  • $p_v = \text{argmin}_{L_v \le k \le R_v} L_k$
  • $q_v = \text{argmax}_{L_v \le k \le R_v} R_k$

즉, $v$에서 한 번의 점프로 갈 수 있는 $[L_v, R_v]$ 구간의 정점 중, $L_k$가 최소인 정점과 $R_k$가 최대인 정점으로 가는 간선, 이렇게 2개만 만드는 것입니다.

Subtask 3에서 만든 그래프를 $G$, 이번에 만든 그래프를 $H$, 그래프 $H$에서 $v$에서 도달 가능한 정점의 집합을 $Reach_H(v)$라고 정의합시다. 이렇게 두 개의 간선만 만들어도 도달 가능한 최소/최대 정점을 계산할 수 있음을 보여야 합니다. 다시 말해, $U = \bigcup_{x \in Reach_H(v)} [L_x, R_x]$가 $Reach_G(v)$와 같음을 보여야 합니다.

먼저 $Reach_G(v) \subseteq U$임을 보이겠습니다.

$v$에서 한 번의 점프로 갈 수 있는 정점 $x$ ($L_v \le x \le R_v$) 로 가면, $[L_x, R_x]$ 구간에 있는 정점으로도 갈 수 있어집니다. 정의에 의해 $L_{p_v} \le L_x \le R_x \le R_{q_v}$가 성립합니다. 또한, $p_v \in [L_v, R_v] \cap [L_{p_v}, R_{p_v}]$, $q_v \in [L_v,R_v] \cap [L_{q_v}, R_{q_v}]$가 성립하므로, 세 구간 $[L_{p_v}, R_{p_v}]$, $[L_v, R_v]$, $[L_{q_v}, R_{q_v}]$의 합집합은 끊어지지 않은 하나의 구간 $[L_{p_v},R_{q_v}]$를 이루며, 이 구간은 $U$에 포함됩니다. 그러므로 $v$에서 두 번 점프해서 도달 가능한 정점은 모두 $U$에 포함됩니다.

그래프 $H$에서 새롭게 도달한 정점마다 같은 과정을 반복합니다. 어떤 정점 $y$에 도달했다면, $G$에서는 $[L_y, R_y]$ 구간의 모든 정점으로 이동할 수 있고, 이 구간의 정점에서 한 번의 점프로 갈 수 있는 정점은 모두 $[L_{p_y}, R_{q_y}]$ 안에 포함됩니다. 그래프 $H$에는 $y$에서 이러한 두 정점 $p_y, q_y$으로 가는 간선이 있으므로, $p_y, q_y \in Reach_H(v)$입니다. 앞에서 본 것과 마찬가지로 $[L_{p_y}, R_{q_y}] \subseteq U$ 라는 것을 알 수 있습니다. 따라서 $U$ 안의 임의의 정점 $z \in [L_y, R_y]$에서 한 번 더 이동해도 $[L_{p_y}, R_{q_y}]$ 안에만 머무르게 되므로 여전히 $U$ 안에 포함됨을 알 수 있습니다.

이 과정을 반복하면 $v$에서 3번, 4번, 또는 그 이상 점프해서 도달할 수 있는 정점도 모두 $U$에 포함됨을 알 수 있습니다. 즉, $Reach_G(v) \subseteq U$입니다.

이제 반대 방향, 즉 $U \subseteq Reach_G(v)$ 임을 보입니다.

$E(H) \subseteq E(G)$ 라는 것을 생각하면 $Reach_H(v) \subseteq Reach_G(v)$임은 쉽게 알 수 있습니다. 모든 정점 $x \in Reach_H(v)$에 대해 $x$에서 $[L_x, R_x]$의 모든 정점으로 가는 간선이 있으므로, $U \subseteq Reach_G(v)$ 또한 성립합니다.

$O(N)$ 시간 전처리 후에 RMQ를 $O(1)$ 시간에 구할 수 있는 자료구조를 사용하면 그래프를 만드는 데 $O(N)$ 시간이 걸리고, SCC와 DP에도 $O(N)$, 그리고 쿼리를 위한 RMQ를 준비하는 데에도 $O(N)$ 시간이 걸립니다. 이후 쿼리는 매번 상수 시간에 처리할 수 있으므로, 전체 시간 복잡도는 $O(N+Q)$입니다.

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;

template<typename T, typename O>
struct linear_rmq{ // https://codeforces.com/blog/entry/78931
    vector<T> v; int n; O o;
    static const int b = 30;
    vector<int> mask, t;
    int op(int x, int y) const { return o(v[x], v[y]) ? x : y; }
    int lsb(int x) const { return x & -x; }
    int msb_index(int x) const { return __builtin_clz(1) - __builtin_clz(x); }
    int small(int r, int size = b) const {
        int dist_from_r = msb_index(mask[r] & ((1<<size)-1));
        return r - dist_from_r;
    }
    linear_rmq(const vector<T> &v) : v(v), n(v.size()), o(), mask(n), t(n) {
        int curr_mask = 0;
        for(int i=0; i<n; i++){
            curr_mask = (curr_mask<<1) & ((1<<b)-1);
            while(curr_mask > 0 && op(i, i - msb_index(lsb(curr_mask))) == i) curr_mask ^= lsb(curr_mask);
            curr_mask |= 1;
            mask[i] = curr_mask;
        }
        for(int i=0; i<n/b; i++) t[i] = small(b*i+b-1);
        for(int j=1; (1<<j)<=n/b; j++) for(int i=0; i+(1<<j)<=n/b; i++) t[n/b*j+i] = op(t[n/b*(j-1)+i], t[n/b*(j-1)+i+(1<<(j-1))]);
    }
    T get(int l, int r) const {
        if (r-l+1 <= b) return v[small(r, r-l+1)];
        int ans = op(small(l+b-1), small(r));
        int x = l/b+1, y = r/b-1;
        if(x <= y){
            int j = msb_index(y-x+1);
            ans = op(ans, op(t[n/b*j+x], t[n/b*j+y-(1<<j)+1]));
        }
        return v[ans];
    }
};

int N, M, Q, L[202020], R[202020];

int K, C[202020], Min[202020], Max[202020];
vector<int> G[202020], G2[202020], T[202020], V;
void AddEdge(int s, int e){ G[s].push_back(e); G2[e].push_back(s); }
void DFS1(int v){
    C[v] = -1;
    for(auto i : G[v]) if(!C[i]) DFS1(i);
    V.push_back(v);
}
void DFS2(int v, int c){
    C[v] = c;
    for(auto i : G2[v]) if(C[i] == -1) DFS2(i, c);
}
void GetSCC(){
    for(int i=1; i<N; i++) if(!C[i]) DFS1(i);
    reverse(V.begin(), V.end());
    for(auto i : V) if(C[i] == -1) DFS2(i, ++K);

    memset(Min, 0x3f, sizeof Min);
    memset(Max, 0xc0, sizeof Max);
    for(int i=1; i<N; i++) Min[C[i]] = min(Min[C[i]], i);
    for(int i=1; i<N; i++) Max[C[i]] = max(Max[C[i]], i);

    for(int i=1; i<N; i++) for(auto j : G[i]) if(C[i] != C[j]) T[C[i]].push_back(C[j]);
    for(int i=K; i>=1; i--) for(auto j : T[i]) Min[i] = min(Min[i], Min[j]), Max[i] = max(Max[i], Max[j]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    iota(L+1, L+N, 1);
    iota(R+1, R+N, 1);
    for(int i=1; i<=M; i++){
        int x, y; cin >> x >> y;
        if(y < x) L[x] = min(L[x], y);
        if(x < y) R[x-1] = max(R[x-1], y-1);
    }

    vector<pair<int,int>> le(N), ri(N);
    for(int i=1; i<N; i++) le[i] = {L[i], i};
    for(int i=1; i<N; i++) ri[i] = {R[i], i};

    linear_rmq<pair<int,int>, less<>> lt(le);
    linear_rmq<pair<int,int>, greater<>> rt(ri);
    for(int i=1; i<N; i++){
        int p = lt.get(L[i], R[i]).second;
        int q = rt.get(L[i], R[i]).second;
        AddEdge(i, p); AddEdge(i, q);
    }
    GetSCC();

    iota(L+1, L+N, 1);
    iota(R+1, R+N, 1);
    for(int i=1; i<N; i++) L[i] = Min[C[i]], R[i] = Max[C[i]];
    linear_rmq<int, less<>> LT(vector<int>(L, L+N+1));
    linear_rmq<int, greater<>> RT(vector<int>(R, R+N+1));

    cin >> Q;
    for(int q=1; q<=Q; q++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        int l = LT.get(a, b-1), r = RT.get(a, b-1) + 1;
        cout << (l <= c && d <= r ? "YES" : "NO") << "\n";
    }
}

만점 풀이 - RMQ, $O(N \log^2 N + Q)$

Observation 3에서 이어집니다. $L_i$와 $R_i$를 구해야 합니다.

상태 $i$에서 $k$번 점프해서 갈 수 있는 상태의 범위를 $[f^k(i), g^k(i)]$라고 합시다. $f^k(\ast)$와 $g^k(\ast)$를 모두 알고 있을 때, $f^{2k}(\ast)$와 $g^{2k}(\ast)$를 구할 수 있다면 문제를 빠르게 해결할 수 있어 보입니다.

$i$에서 $2k$번 점프해서 갈 수 있는 상태의 범위는, $[f^k(i), g^k(i)]$ 범위 안에 있는 임의의 상태에서 $k$번 점프해서 갈 수 있는 상태들의 합집합과 같습니다. 따라서 RMQ를 이용해 다음과 같이 계산할 수 있습니다.

  • $f^{2k}(i) = \min_{x=f^k(i)}^{g^k(i)} f^k(x)$
  • $g^{2k}(i) = \min_{x=f^k(i)}^{g^k(i)} f^k(x)$

Sparse table이나 Segment tree를 이용하면 $k \rightarrow 2k$ 전이를 $O(N \log N)$ 시간에 할 수 있습니다. $k = 1$에서 시작해 $O(\log N)$ 단계를 거치면 $O(N \log^2 N)$ 시간에 $L_i$와 $R_i$를 구할 수 있습니다. 쿼리는 SCC 풀이와 마찬가지로 Sparse table을 이용하면 $O(N \log N)$ 전처리 후에 매번 $O(1)$ 시간에 답을 구할 수 있습니다.

전체 시간 복잡도는 $O(N \log^2 N + Q)$입니다.

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
#include <bits/stdc++.h>
using namespace std;

template<typename T, typename O>
struct sparse_table{
    int n; vector<vector<T>> t; O op;
    T f(const T &x, const T &y) const { return op(x, y) ? x : y; }
    sparse_table(vector<T> a) : n(a.size()), t(__lg(n)+1, vector<T>(n)), op() {
        copy(a.begin(), a.end(), t[0].begin());
        for(int i=1; i<t.size(); i++) for(int j=0; j+(1<<i)-1<n; j++) t[i][j] = f(t[i-1][j], t[i-1][j+(1<<(i-1))]);
    }
    T get(int l, int r) const {
        int k = __lg(r-l+1);
        return f(t[k][l], t[k][r-(1<<k)+1]);
    }
};

int N, M, Q, L[22][202020], R[22][202020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    iota(L[0]+1, L[0]+N, 1);
    iota(R[0]+1, R[0]+N, 1);
    for(int i=1; i<=M; i++){
        int x, y; cin >> x >> y;
        if(y < x) L[0][x] = min(L[0][x], y);
        if(x < y) R[0][x-1] = max(R[0][x-1], y-1);
    }

    for(int k=1; k<22; k++){
        sparse_table<int, less<>> LT(vector<int>(L[k-1], L[k-1]+N));
        sparse_table<int, greater<>> RT(vector<int>(R[k-1], R[k-1]+N));
        for(int i=1; i<N; i++) L[k][i] = LT.get(L[k-1][i], R[k-1][i]);
        for(int i=1; i<N; i++) R[k][i] = RT.get(L[k-1][i], R[k-1][i]);
    }

    sparse_table<int, less<>> LT(vector<int>(L[21], L[21]+N));
    sparse_table<int, greater<>> RT(vector<int>(R[21], R[21]+N));

    cin >> Q;
    for(int q=1; q<=Q; q++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        int l = LT.get(a, b-1), r = RT.get(a, b-1) + 1;
        cout << (l <= c && d <= r ? "YES" : "NO") << "\n";
    }
}

다른 풀이

이밖에도 적당한 전처리를 한 뒤 쿼리의 결과를 캐싱하는 식으로 경로 압축과 비슷하게 구현하면 실제로 $O(Q + N\sqrt Q)$개의 $(a, b)$ 쌍만 캐싱하게 되어 $O((N+M+Q+N\sqrt Q) \log N)$ 정도 시간에 문제를 푸는 방법이 있고, 스택을 이용해 정점과 간선이 $O(N)$개인 그래프를 만드는 $O(N+Q)$ 풀이도 존재합니다.

고등부 4번. 공장

Subtask 1. $N \le 20$ (13점)

직원을 선택하는 $O(2^N)$가지 경우를 모두 확인하면서, 각 케이스마다 $O(N \log N)$ 정도에 점수를 계산하면 됩니다. 이 서브태스크를 해결하면서 $D_i$가 같은 직원은 항상 짝수 명씩 고용해야 한다는 점을 알아가면 좋습니다.

이렇게 지문이 복잡하고 등장하는 변수가 많은 경우, 완전 탐색을 구현해 보면서 문제를 명확하게 이해하는 것도 좋은 전략입니다.

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
#include <bits/stdc++.h>
using namespace std;

struct Info{
    int a, b, c, id;
    Info() = default;
    Info(int a, int b, int c, int id) : a(a), b(b), c(c), id(id) {}
    bool operator < (const Info &t) const { return a < t.a; }
};

int N, T, A[22], B[22], C[22], D[22];
vector<Info> V[22];

int f(vector<int> v){
    for(int i=1; i<=T; i++) V[i].clear();

    for(auto i : v) V[D[i]].emplace_back(A[i], B[i], C[i], i);
    for(int i=1; i<=T; i++) sort(V[i].begin(), V[i].end());
    for(int i=1; i<=T; i++) if(V[i].size() % 2 != 0) return -1e9;

    int res = 0;
    for(auto i : v) res -= C[i];
    for(int i=1; i<=T; i++) for(int j=0; j<V[i].size(); j+=2) res += V[i][j+1].b - V[i][j].b;

    vector<Info> vec;
    for(int i=0; i<=T; i++){
        vec.clear();
        merge(V[i].begin(), V[i].end(), V[i+1].begin(), V[i+1].end(), back_inserter(vec));
        for(int j=0; j<vec.size(); j+=2) res -= vec[j+1].a - vec[j].a;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> T;
    for(int i=0; i<N; i++) cin >> A[i] >> B[i] >> C[i] >> D[i];

    int mx = 0, pos = 0;
    for(int bit=1; bit<(1<<N); bit++){
        vector<int> v;
        for(int i=0; i<N; i++) if(bit >> i & 1) v.push_back(i);
        int now = f(v);
        if(now > mx) mx = now, pos = bit;
    }
    cout << mx << "\n" << __builtin_popcount(pos) << "\n";
    for(int i=0; i<N; i++) if(pos >> i & 1) cout << i + 1 << " ";
}

Subtask 2. $T = 1$ (27점)

0일차 밤, 1일차 낮, 1일차 밤만 고려하면 됩니다. 모든 직원을 $A$ 내림차순으로 정렬합시다.

직원을 앞에서부터 보면서, 각 직원을 선택할지 말지 결정하는 DP를 생각합시다. 구체적으로, 점화식을 아래와 같이 정의할 수 있습니다.

  • $D(i, 0) = $ $1, \cdots, i$번 직원 중 짝수 명 선택했을 때 가능한 최대 점수
  • $D(i, 1) = $ $1, \cdots, i$번 직원 중 홀수 명 선택했을 때 가능한 최대 점수

$i$번째 직원이 홀수 번째로 선택된 직원이라면, 한 번의 야간 근무에서 $A_i$ 만큼의 야간 수당, 주간 생산에서 $B_i$ 만큼의 생산 이익, 그리고 기본 임금이 $C_i$ 만큼 발생합니다. 따라서 점수에 $-2A_i + B_i - C_i$ 만큼 기여합니다.

$i$번째 직원이 짝수 번째로 선택된 직원이라면, 한 번의 야간 근무에서 $-A_i$ 만큼의 야간 수당, 주간 생산에서 $-B_i$ 만큼의 생산 이익, 그리고 기본 임금이 $C_i$ 만큼 발생합니다. 따라서 점수에 $2A_i - B_i - C_i$ 만큼 기여합니다.

따라서 점화식은 아래와 같이 계산할 수 있습니다.

  • $D(i, 1) = \max \lbrace D(i-1, 1), D(i-1, 0) - 2A_i + B_i - C_i \rbrace$
  • $D(i, 0) = \max \lbrace D(i-1, 0), D(i-1, 1) + 2A_i - B_i - C_i \rbrace$

동적 계획법은 $O(N)$ 이지만, 직원을 정렬해야 하므로 전체 시간 복잡도는 $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
#include <bits/stdc++.h>
using namespace std;

struct Info{
    int a, b, c, id;
    Info() = default;
    Info(int a, int b, int c, int id) : a(a), b(b), c(c), id(id) {}
    bool operator < (const Info &t) const { return a < t.a; }
};

int N, T, D[555][2], P[555][2];
Info A[555];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> T;
    for(int i=1,d; i<=N; i++) cin >> A[i].a >> A[i].b >> A[i].c >> d, A[i].id = i;
    sort(A+1, A+N+1, [](auto x, auto y){ return x.a > y.a; });

    memset(D, 0xc0, sizeof D); D[0][0] = 0;
    for(int i=1; i<=N; i++){
        int  odd = -A[i].a*2 + A[i].b - A[i].c;
        int even = +A[i].a*2 - A[i].b - A[i].c;
        D[i][0] = D[i-1][0]; D[i][1] = D[i-1][1];
        if(D[i-1][0] +  odd > D[i][1]) D[i][1] = D[i-1][0] +  odd, P[i][1] = 1;
        if(D[i-1][1] + even > D[i][0]) D[i][0] = D[i-1][1] + even, P[i][0] = 1;
    }

    int mx = D[N][0], j = 0;

    vector<int> res;
    for(int i=N; i; j^=P[i--][j]) if(P[i][j]) res.push_back(A[i].id);

    cout << mx << "\n" << res.size() << "\n";
    for(auto i : res) cout << i << " ";
}

Subtask 3. $T \le 10$ (47점)

Subtask 2의 풀이와 비슷합니다. $T \le 10$으로 매우 작으므로, 각 날짜마다 고용된 직원 수의 홀짝을 비트로 관리하는 비트 DP를 구현하면 $O(N2^T)$ 시간에 문제를 해결할 수 있습니다.

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
#include <bits/stdc++.h>
using namespace std;

struct Info{
    int a, b, c, d, id;
    Info() = default;
    Info(int a, int b, int c, int d, int id) : a(a), b(b), c(c), d(d), id(id) {}
    bool operator < (const Info &t) const { return a < t.a; }
};

int N, T, D[555][1<<11], P[555][1<<11];
Info A[555];

int f(int bit, int p){ return bit >> p & 1; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> T;
    for(int i=1; i<=N; i++) cin >> A[i].a >> A[i].b >> A[i].c >> A[i].d, A[i].id = i;
    sort(A+1, A+N+1, [](auto x, auto y){ return x.a > y.a; });

    memset(D, 0xc0, sizeof D); D[0][0] = 0;
    for(int i=1; i<=N; i++){
        for(int bit=0; bit<(1<<11); bit++){
            D[i][bit] = D[i-1][bit];
            int cost = -A[i].c, prv = bit ^ (1 << A[i].d);

            if(f(bit, A[i].d)) cost += A[i].b;
            else cost -= A[i].b;

            if(f(bit, A[i].d-1) != f(bit, A[i].d)) cost -= A[i].a;
            else cost += A[i].a;

            if(f(bit, A[i].d) != f(bit, A[i].d+1)) cost -= A[i].a;
            else cost += A[i].a;

            if(D[i-1][prv] + cost > D[i][bit]) D[i][bit] = D[i-1][prv] + cost, P[i][bit] = 1;
        }
    }

    vector<int> res;
    for(int i=N, bit=0; i; i--){
        if(!P[i][bit]) continue;
        res.push_back(A[i].id);
        bit ^= 1 << A[i].d;
    }

    cout << D[N][0] << "\n" << res.size() << "\n";
    for(auto i : res) cout << i << " ";
}

Subtask 4. 각 날짜마다 지원자 8명 이하 (69점)

각 날짜마다 지원자가 8명 이하라는 점을 이용해 비트 DP를 설계해 봅시다. 편의상 $M = 8$이라고 합시다.

$i$일차 지원자 선발 여부가 $bit$일 때, ($i$일차 낮에 얻는 생산 이익) - ($i$일차 지원자의 기본 임금)의 값을 $Day(i, bit)$라고 정의합시다. 각 날짜별로 지원자를 $A$ 내림차순으로 미리 정렬해 두면 $O(M2^MT)$ 시간에 $Day(i, bit)$를 모두 계산할 수 있습니다. 사실 크기가 짝수인 집합만 봐도 되므로 연산량은 절반이 됩니다.

$i$일차 지원자 선발 여부가 $x$, $i-1$일차 지원자 선발 여부가 $y$일 때, $i$일차 밤에 지급해야 하는 야간 수당을 $Nighg(i, x, y)$라고 정의합시다. $O(M^24^MT)$ 시간에 계산할 수 있고, 마찬가지로 크기가 짝수인 집합만 보면 연산량은 1/4가 됩니다.

$D(i, bit) := $ $i$일차의 지원자 선발 여부가 $bit$일 때, $0$일차 밤부터 $i$일차 낮까지 얻을 수 있는 최대 점수라고 정의합시다. $i$일차 밤에 지급되는 야간 수당은 $i+1$일차 지원자가 결정되어야 알 수 있으므로 $D(i, bit)$에서는 $i$일차 낮까지만 고려합니다.

상태 전이는 $D(i, x) \leftarrow D(i-1, y) + Day(i, x) - Night(i, x, y)$와 같이 표현할 수 있습니다. 점화식은 $O(4^MT)$ 시간에 계산할 수 있습니다.

따라서 $O(N \log N + M^2 4^M T)$ 정도 시간에 전체 문제를 해결할 수 있습니다.

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
78
79
80
#include <bits/stdc++.h>
using namespace std;
int f(int bit, int p){ return bit >> p & 1; }

struct Info{
    int a, b, c, id;
    Info() = default;
    Info(int a, int b, int c, int id) : a(a), b(b), c(c), id(id) {}
    bool operator < (const Info &t) const { return a < t.a; }
    bool operator > (const Info &t) const { return a > t.a; }
};

int N, T, D[555][1<<8], P[555][1<<8];
vector<Info> A[555];
int Day[1<<8], Night[1<<8][1<<8], POP[1<<8];

void Calc(int d){
    int n = A[d].size(), m = A[d-1].size();
    memset(Day, 0, sizeof Day);
    for(int bit=0; bit<(1<<n); bit++){
        if(POP[bit] % 2) continue;
        int cnt = 0;
        for(int i=0; i<n; i++){
            if(~bit >> i & 1) continue;
            Day[bit] -= A[d][i].c;
            if(cnt == 0) Day[bit] += A[d][i].b, cnt ^= 1;
            else Day[bit] -= A[d][i].b, cnt ^= 1;
        }
    }

    memset(Night, 0, sizeof Night);
    for(int x=0; x<(1<<n); x++){
        if(POP[x] % 2) continue;
        for(int y=0; y<(1<<m); y++){
            if(POP[y] % 2) continue;
            int cnt = 0, i = 0, j = 0;
            while(i < n || j < m){
                int v = -1;
                if(j == m || i < n && A[d][i].a > A[d-1][j].a) v = x >> i & 1 ? A[d][i].a : -1, i++;
                else v = y >> j & 1 ? A[d-1][j].a : -1, j++;
                if(v == -1) continue;
                if(cnt == 0) Night[x][y] -= v, cnt ^= 1;
                else Night[x][y] += v, cnt ^= 1;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> T;
    for(int i=1; i<=N; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        A[d].emplace_back(a, b, c, i);
    }
    for(int i=1; i<=N; i++) sort(A[i].begin(), A[i].end(), greater<>());

    for(int i=1; i<(1<<8); i++) POP[i] = POP[i^(i&-i)] + 1;

    memset(D, 0xc0, sizeof D); D[0][0] = 0;
    for(int d=1; d<=T+1; d++){
        Calc(d);
        for(int x=0; x<(1<<A[d].size()); x++){
            if(POP[x] % 2) continue;
            for(int y=0; y<(1<<A[d-1].size()); y++){
                if(POP[y] % 2) continue;
                int cost = Day[x] + Night[x][y];
                if(D[d-1][y] + cost > D[d][x]) D[d][x] = D[d-1][y] + cost, P[d][x] = y;
            }
        }
    }

    vector<int> res;
    for(int i=T+1, bit=0; i; bit=P[i--][bit]){
        for(int j=0; j<A[i].size(); j++) if(bit >> j & 1) res.push_back(A[i][j].id);
    }

    cout << D[T+1][0] << "\n" << res.size() << "\n";
    for(auto i : res) cout << i << " ";
}

Subtask 5. 추가 제약 조건 없음 (100점)

TODO: 풀이 작성 예정

아래는 $O(V^2E)$ Dinic algorithm을 사용한 코드지만, DFS를 이용한 $O((V+E)F)$ 또는 $O(V^2F)$ Ford-Fulkerson method의 구현이나 $O(V^2E)$ Edmonds-Karp algorithm을 사용하더라도 시간 안에 여유롭게 문제를 해결할 수 있습니다.

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<typename flow_t, flow_t MAX_U=(1<<30), bool scale=false>
struct Dinic{
    struct edge_t{ int v, r; flow_t c, f; };
    int n;
    vector<vector<edge_t>> g;
    vector<int> lv, idx;
    Dinic(int n) : n(n) {
        static_assert(is_integral<flow_t>::value);
        static_assert(!scale || __builtin_popcountll(MAX_U) == 1);
        clear();
    }
    void clear(){
        g = vector<vector<edge_t>>(n);
        lv = vector<int>(n, 0);
        idx = vector<int>(n, 0);
    }
    void add_edge(int s, int e, flow_t c1, flow_t c2=flow_t(0)){
        g[s].push_back({e, (int)g[e].size(), c1, 0});
        g[e].push_back({s, (int)g[s].size()-1, c2, 0});
    }
    bool bfs(int s, int t, flow_t limit=1){
        fill(lv.begin(), lv.end(), 0);
        queue<int> que; que.push(s); lv[s] = 1;
        while(!que.empty()){
            int v = que.front(); que.pop();
            for(const auto &e : g[v]) if(!lv[e.v] && e.c - e.f >= limit) que.push(e.v), lv[e.v] = lv[v] + 1;
        }
        return lv[t] != 0;
    }
    flow_t dfs(int v, int t, flow_t fl=MAX_U){
        if(v == t || fl == flow_t(0)) return fl;
        for(int &i=idx[v]; i<g[v].size(); i++){
            auto &e = g[v][i];
            if(lv[e.v] != lv[v] + 1 || e.c - e.f == flow_t(0)) continue;
            flow_t now = dfs(e.v, t, min(fl, e.c - e.f));
            if(now == flow_t(0)) continue;
            e.f += now; g[e.v][e.r].f -= now;
            return now;
        }
        return 0;
    }
    flow_t maximum_flow(int s, int t){
        flow_t flow = 0, augment = 0;
        if(!scale){
            while(bfs(s, t)){
                fill(idx.begin(), idx.end(), 0);
                while((augment=dfs(s, t)) != flow_t(0)) flow += augment;
            }
        }
        else{
            for(flow_t f=MAX_U; f; f/=2){
                while(bfs(s, t, f)){
                    fill(idx.begin(), idx.end(), 0);
                    while((augment=dfs(s, t)) != flow_t(0)) flow += augment;
                }
            }
        }
        return flow;
    }
    tuple<flow_t, vector<int>, vector<int>, vector<pair<int,int>>> minimum_cut(int s, int t){
        flow_t flow = maximum_flow(s, t);
        vector<int> a, b;
        vector<pair<int,int>> edges;
        bfs(s, t, 1);
        for(int i=0; i<n; i++) (lv[i] ? a : b).push_back(i);
        for(auto i : a) for(auto e : g[i]) if(e.c != flow_t(0) && !lv[e.v]) edges.emplace_back(i, e.v);
        return {flow, a, b, edges};
    }
};

struct Info{
    int a, b, c, id;
    Info() = default;
    Info(int a, int b, int c, int id) : a(a), b(b), c(c), id(id) {}
    bool operator < (const Info &t) const { return a < t.a; }
};

int N, T, W[1010], cnt;
vector<Info> V[555];
vector<int> ID[555];
vector<tuple<int,int,int>> E;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> T;
    for(int i=1; i<=N; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        V[d].emplace_back(a, b, c, i);
    }
    for(int i=0; i<=T+1; i++) V[i].emplace_back(-1, 0, 0, -1), V[i].emplace_back(1001, 0, 0, -1);
    for(int i=1; i<=T; i++) sort(V[i].begin(), V[i].end());

    for(int i=0; i<=T+1; i++){
        ID[i].resize(V[i].size()-1);
        for(auto &j : ID[i]) j = cnt++;
    }
    for(int i=1; i<=T; i++){
        int sz = V[i].size() - 2;
        if(!sz) continue;
        // face
        for(int j=1; j<sz; j++) W[ID[i][j]] = V[i][j+1].b - V[i][j].b;
        // horizontal edge
        for(int j=1; j<=sz; j++){
            E.emplace_back(ID[i][j-1], ID[i][j], V[i][j].c);
        }
    }

    for(int i=1; i<=T+1; i++){
        if(V[i-1].empty() || V[i].empty()) continue;
        for(int x=0, y=0; x+1<V[i-1].size() && y+1<V[i].size(); ){
            int s1 = V[i-1][x].a, e1 = V[i-1][x+1].a;
            int s2 = V[i][y].a, e2 = V[i][y+1].a;
            int len = min(e1, e2) - max(s1, s2);
            if(len > 0) E.emplace_back(ID[i-1][x], ID[i][y], len);
            if(e1 < e2) x++; else y++;
        }
    }

    const int src = cnt++, snk = cnt++;
    Dinic<int> G(cnt);
    for(auto [u,v,w] : E) G.add_edge(u, v, w, w);
    G.add_edge(ID[0][0], snk, 1e9);
    G.add_edge(ID[T+1][0], snk, 1e9);
    for(int i=1; i<=T; i++){
        int sz = V[i].size() - 2;
        G.add_edge(ID[i][0], snk, 1e9);
        if(!sz) continue;
        for(int j=1; j<sz; j++){
            int id = ID[i][j];
            if(W[id] > 0) G.add_edge(src, id, +W[id]);
            if(W[id] < 0) G.add_edge(id, snk, -W[id]);
        }
        G.add_edge(ID[i][sz], snk, 1e9);
    }

    int sum = 0;
    for(int i=0; i<cnt; i++) sum += max(0, W[i]);

    auto [cost,le,ri,edges] = G.minimum_cut(src, snk);
    cout << sum - cost << "\n";

    vector<int> res;
    for(int i=1; i<=T; i++){
        int sz = V[i].size() - 2;
        if(!sz) continue;
        for(int j=1; j<=sz; j++){
            bool x = binary_search(le.begin(), le.end(), ID[i][j-1]);
            bool y = binary_search(le.begin(), le.end(), ID[i][j]);
            if(x != y) res.push_back(V[i][j].id);
        }
    }
    cout << res.size() << "\n";
    for(auto i : res) cout << i << " ";
}