서론

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$를 복원하여 문제를 해결할 수도 있습니다.

#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개일 때를 조심해서 구현해야 합니다.

#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)$ 시간에 문제를 해결할 수 있습니다.

#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가 승리할 수 있습니다. 따라서 다음과 같은 방식을 생각해 볼 수 있습니다.

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

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

#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)$를 모두 계산할 수 있습니다.

#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)$ 시간에 가능합니다.

#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$로 만들기 위해 필요한 조건은 다음과 같습니다.

$i < j$, $A_i > A_j$이고 $A_i,A_j \in B$ 이면 $P(A_i) < P(A_j)$
$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$번 이하인지는 다시 확인하는 게 좋습니다.

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

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

#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$은 최댓값의 위치)

$H_i > t$인 정점
$1, R(1), R^2(1), \cdots, m$ 중 $H_i \le t$인 정점 (prefix max)
$N, L(N), L^2(N), \cdots, m$ 중 $H_i \le t$인 정점 (suffix max)
$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$인 문제를 해결할 수 있지만, 이후 단계로 발전시키기 어렵습니다.

#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]$ 구간에서 최댓값의 위치)

$l \le i \le r$ 이면서 $H_i > t$인 정점
$l, R(l), R^2(l), \cdots, m$ 중 $H_i \le t$인 정점 (구간의 prefix max)
$r, L(r), L^2(r), \cdots, m$ 중 $H_i \le t$인 정점 (구간의 suffix max)
$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가 필요해 집니다.

#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

$l \le i \le r$ 이면서 $H_i > t$인 정점
$l, R(l), R^2(l), \cdots, m$ 중 $H_i \le t$인 정점 (구간의 prefix max)
$r, L(r), L^2(r), \cdots, m$ 중 $H_i \le t$인 정점 (구간의 suffix max)
$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)$ 시간에 문제를 해결할 수 있습니다.

#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 관련 로직을 확인하시길 바랍니다.

#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$)

$\text{DnC}(l,m)$
$\text{DnC}(m+1,r)$
$[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 입니다.

#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)$입니다.

#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)$입니다.

#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)$입니다.

#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)$입니다.

#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$가 같은 직원은 항상 짝수 명씩 고용해야 한다는 점을 알아가면 좋습니다.

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

#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)$입니다.

#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)$ 시간에 문제를 해결할 수 있습니다.

#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)$ 정도 시간에 전체 문제를 해결할 수 있습니다.

#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을 사용하더라도 시간 안에 여유롭게 문제를 해결할 수 있습니다.

#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 << " ";
}

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

댓글