JOISC 2017 Day 2-3. Railway Trip

https://www.acmicpc.net/problem/17697

17697번: Railway Trip

$N$개의 역이 일렬로 있으며, $i$번 역의 등급은 $A_i$이다. 모든 $A_i$에 대해 $1 \le A_i \le K$가 성립한다. $K$개의 노선이 있으며, 각 노선은 등급이 $A_i$ 이상인 역에 정차한다. 각 노선은 정방향과 역방향 모두 존재한다. $Q$개의 쿼리가 주어진다. 쿼리에는 두 역 번호가 주어진다. 한 역에서 다른 역으로 이동할 때, 거쳐야 하는 중간 역의 최소 수를 구하여라. 환승은 언제든지 가능하며, 중간 역은 기차가 실제로 정차하는 역만 센다.

이런 유형의 문제는 꽤 자주 출제된 바 있다. (UCPC 2019 %, Google Code Jam 2020 Round 2 Emacs++) 이 중 구글 코드 잼 문제는 내가 대회 때 섭테 하나조차 긁지 못했던 아픈 기억이 있다. (섭테 1이 앞의 % 문제와 정확히 동치이다.) 어려운 문제 유형인 것은 맞지만 많이 나왔기 때문에 풀이를 이해할 필요가 있다고 생각했고, 우연찮게도 국대교육에 비슷한 문제가 나와서 풀이를 해보려고 한다. 이 글은 공식 Editorial을 참고해 이해하기 쉽도록 재구성하였다.

 

먼저 생각해야 하는 것은 그래프를 이용한 풀이이다. 모든 노선에 대해 모든 인접한 역을 그래프로 만들면 최단 거리 문제가 된다. 그러나 이 방식에는 몇 가지 문제가 있는데, 일단 매 쿼리마다 다익스트라를 돌려야 한다는 것이고, 간선 개수도 최대 $O(NK)$개까지 될 수 있다는 점이다.

 

위와 같이 각 역을 역의 등급이 높을수록 더 높은 막대로 표시할 수 있다. 이때 노선에서의 이동은 저 그림 위에서는 중간에 아무 막대도 교차하지 않는 특정 선분을 잡고, 왼쪽 끝에서 오른쪽 끝으로 이동하는 것과 같은 형태로 그려진다. 이때 빨간 선 아래에 있는 모든 막대의 높이는 이 선의 높이보다 작아야 한다. 이것을 한 이동이라고 생각하자.

 

앞에서 보았다시피 가능한 총 이동의 개수는 $O(NK)$개라고 생각하기 쉽다. 그러나 이들 중 시작점과 끝점이 겹치지 않는 것만 세면 그 개수는 크게 줄어든다. 아래 그림과 같이, $NK$는 한 쌍의 점 간의 이동이 여러 번 세어진 결과이다.

 

만약 저렇게 한 이동이 여러 번 세어지는 경우를 방지하기 위해, 모든 이동은 양쪽 두 막대 중 적어도 한 쪽의 꼭대기를 지나야 한다고 생각하자. 그렇게 해도 이동의 종류는 변하지 않는다. 이렇게 이동의 종류를 간소화하고 나면 위 그림에서 가능한 모든 이동은 아래와 같이 나타난다.

 

이제 가능한 이동의 개수가 $O(N)$개임을 보인다. 모든 이동은 양쪽 정점 중 하나의 꼭대기를 지난다. 한 정점 $x$의 꼭대기를 지나는 이동의 개수는 왼쪽으로 한 개, 오른쪽으로 한 개, 최대 두 개이다. 양쪽으로 가면서 자신 이상의 높이를 가진 막대 중 처음으로 나오는 것을 찾으면 된다. 이렇게 그래프에서 간선이 최대 $2N$개인 것을 증명했다. 이제 다익스트라를 돌리면 Subtask 2까지 해결할 수 있다.

 

여기서 간선을 더 줄이는 것은 불가능하고, Subtask 3부터는 경로의 형태에 대한 관찰을 해야 한다. 아래 그림과 같이 경로의 형태를 보면 높이가 가장 높은 어느 지점까지는 올라가기만 한 뒤 그 이후는 내려가기만 할 것이라고 생각할 수 있다. 만약 도중에 내려갔다 다시 올라간다면, 그냥 높은 노선을 타고 쭉 가는 것이 항상 이득임은 어렵지 않게 생각할 수 있다. (당연히 중간에 거치는 역 수가 더 적기 때문에...)

여기서 중요한 건 올라가는 최대 높이이다. 어느 높이까지 올라갈지를 알 수 있다면, (왼쪽 정점에서 올라가는 데 걸리는 거리) + (오른쪽 정점에서 올라가는 데 걸리는 거리) + (가장 높은 높이에서 이동한 거리) 정도로 답을 간단히 나타낼 수 있다. 그런데 이 높이를 위 그림에서 이야기하는 것은 쉽지 않다. 다른 그림을 준비하기 위해 위 그림의 특성에 대해 분석해 보자. 위 그림의 간선을 수직선 상의 어떤 구간으로 생각할 수 있다. 이때 모든 구간은 서로 포함하거나, 교집합이 (양 끝점을 제외하면) 없는 구조를 하고 있다. 이런 구조는 트리로 모델링할 수 있음이 잘 알려져 있다.

 

위 그림과 같이 트리로 모델링할 것이다. 이때 직사각형의 색은 트리상에서 해당 구간에 대응되는 정점의 깊이를 나타낸다. 대략 빨강 = 0, 주황 = 1, 초록 = 2, 파랑 = 3 정도로 생각하면 좋다. 주의할 점은, 트리의 높이는 실제 막대의 높이와는 관련없고, 오로지 자기 구간을 온전히 포함하는 구간의 개수에만 관련있다는 것이다. 위 그림에서 각 색을 서로 다른 노선이라고 생각하는 것이 좋다. 오른쪽 세 구간을 다른 색(예컨대 주황색 2개/초록색 1개)로 색칠했을 경우 이후의 처리가 굉장히 껄끄러워지므로, 일단 실제 높이에 상관없이 트리상의 깊이에 따라 구간을 분류한다는 사실을 받아들이고 이후의 풀이를 보자.

 

이렇게 정의하고 나면 한 간선(위 그림에서 직사각형)의 깊이를 정의할 수 있다. 또한 각 역을 끝점으로 가지는 구간 중에서 가장 낮은 것을 바탕으로 역의 깊이를 정의할 수 있다. 예를 들어 위 그림에서 왼쪽에서 1번째, 5번째, 10~13번째 역의 깊이는 0이고, 왼쪽에서 3, 4, 9번째 역의 깊이는 1이고, 이런 식이다. 이때 깊이 $x>0$인 역의 좌우에 항상 깊이 $y$ ($y<x$)인 역이 하나 이상씩 존재한다는 것을 확인할 수 있다. 그 이유는 간선의 깊이를 자기 간선의 구간을 포함하는 구간 개수로 정의했기 때문에 자명하다.

 

이제 최단거리를 구하는 방법을 살펴보자. 위 그림에서 보라색 두 점 사이의 최단 거리를 찾는다. 이때 형태가 트리가 되었으므로, LCA 역시 정의할 수 있다. LCA를 다음과 같이 정의한다. 두 정점 $x$와 $y$의 LCA는 범위에 $x$와 $y$를 포함하는 가장 낮은 구간이다. 여기서는 주황색 구간이 LCA임을 알 수 있다. 우리는 최단거리를 구할 때 LCA보다 높게 올라갈 필요가 없음을 알 수 있다. 이미 LCA 구간 $[l, r]$에서 $l \le x, y \le r$이 성립하는데, 더 올라가봤자 이득볼 게 하나도 없다.

 

그렇다면, 최대 높이가 항상 이 LCA 구간인가? 그것도 아니다. 아래와 같은 케이스를 생각해 보자.

 

위 케이스에서는 빨간색 구간이 LCA 구간이지만, 실제로 최적해는 초록->주황 루트로 두 번만에 도착하는 것이다. 이것은 LCA 구간을 실제로 거치지 않는 최적해가 존재할 수 있음을 암시한다. LCA 구간의 깊이가 $d$라고 할 때, $d+1$ 깊이를 가진 구간들 중 그 끝점이 $x$와 $y$ 사이에 위치한 것이 적어도 하나 있을 것이다. 위 그림에서는 $x=3$인 부분, 두 주황색 구간 사이의 부분이 여기에 해당한다. 이 지점을 LCA 구간을 거치지 않고 지나가려면, 결국 이 지점에 정차할 수밖에 없다는 결론에 다다른다. 이 지점의 높이는 $d+1$이므로, 결국 높이가 $d$ 또는 $d+1$인 지점을 하나 이상 지나야 한다는 것을 알아냈다.

 

마지막으로 한 가지 케이스만 더 보자.

 

위 케이스는 조금 특별한데, 그 이유는 LCA 구간이 실제로는 존재하지 않는 전체구간 $[1, N]$이기 때문이다. 전체구간을 그림에 그려준 이유는 이 때문이다. 이런 경우 실제로 저 구간을 지나는 건 말이 안 되므로, $d+1$인 지점을 지나는 특수 케이스의 일종으로 생각해 주면 된다.

 

여기까지 정보를 종합해 보면, 최단 거리는 다음 두 가지 중 하나다. (편의상 $x<y$라고 하자.)

• Case 1) LCA 구간의 왼쪽 끝점에 도착한 뒤, LCA 구간을 타고 오른쪽 끝점으로 와서, 다시 도착점으로 되돌아간다. (단, LCA 구간은 전체 구간이 아니다.)
• Case 2) LCA 구간이 깊이 $d$일 때, 깊이 $d+1$이고 시작점을 포함하는 구간의 오른쪽 끝점으로 이동한다. 이후 깊이 $d+1$이고 끝점을 포함하는 구간의 왼쪽 끝점까지 깊이 $d+1$인 구간만을 이용해 이동하고, 그 뒤 끝점으로 이동한다.

위 두 케이스를 그리면 아래와 같다.

 

Case 1

Case 2

Case 2의 또 다른 예시. Case 2에서 항상 오른쪽으로 이동한다고 착각할 수 있기 때문에 추가했다.

이제 남은 것은 어떤 시작점 $x$에서, 해당 시작점 $x$를 포함하는 깊이 $d$의 구간의 양 끝점까지의 최단 거리를 빠르게 구하는 일이다. 이것을 대충 $O(NK)$ 정도에 하게 되면 Subtask 3이 풀린다. 어차피 깊이 $d$에서 $d-2$로 가려면 $d-1$을 거쳐야 하므로, $d$에서 $d-1$ 양쪽 끝까지의 거리를 구해놓고, 거기서 $d-2$ 양쪽 끝까지 가는 4가지 케이스를 분석하며 DP를 업데이트하는 느낌으로 처리한다. 그러나 여기까지 왔으면 Subtask 4 풀이가 쉬운데, 이걸 Sparse Table로 똑같이 해 주면 된다. 여기까지 할 수 있으면 문제의 남은 부분은 매우 쉽고, 문제가 풀린다. 시간 복잡도는 $O((N+Q) \log K \log N)$이다. 

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
void makeInterval();
void makeSps();
void answerQuery();

int main(){
    input();
    makeInterval();
    makeSps();
    answerQuery();
}

int n, k, q;
int arr[100002];

void input(){
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
}


/// 구간에 대한 정보
struct Interval{
    int l, r, depth, idx;
    Interval(){}
    Interval(int l, int r, int depth, int idx): l(l), r(r), depth(depth), idx(idx){}
} intv[200002];

bool cmp_location(const Interval &a, const Interval &b){
    if(a.l != b.l) return a.l < b.l;
    return a.r > b.r;
}

bool cmp_index(const Interval &a, const Interval &b){
    return a.idx < b.idx;
}

int l;
int depth[200002], par[200002], LCADB[200002][20];
int depthV[100002], intvL[100002], intvR[100002];

void makeInterval(){
    map<pair<int, int>, bool> mp; /// 이미 이 구간을 찾았는지?
    vector<pair<int, int> > vec; /// 스택

    for(int i=1; i<=n; i++){
        while(!vec.empty() && vec.back().second < arr[i]) vec.pop_back();
        if(!vec.empty()){
            int x = vec.back().first, y = i;
            if(!mp[make_pair(x, y)]){
                mp[make_pair(x, y)] = 1;
                l++;
                intv[l] = Interval(x, y, 0, l); /// 처음에는 depth 0으로 둔다
            }
        }
        vec.push_back(make_pair(i, arr[i]));
    }

    vec.clear();

    for(int i=n; i>=1; i--){
        while(!vec.empty() && vec.back().second < arr[i]) vec.pop_back();
        if(!vec.empty()){
            int x = i, y = vec.back().first;
            if(!mp[make_pair(x, y)]){
                mp[make_pair(x, y)] = 1;
                l++;
                intv[l] = Interval(x, y, 0, l); /// 처음에는 depth 0으로 둔다
            }
        }
        vec.push_back(make_pair(i, arr[i]));
    }

    /// 이제 구간의 깊이를 찾고 부모 구간을 찾는다
    sort(intv+1, intv+l+1, cmp_location);
    vector<Interval> stk (1, Interval(1, n, 0, 0));
    for(int i=1; i<=l; i++){
        while(stk.back().r < intv[i].r) stk.pop_back();
        int idx = intv[i].idx;
        intv[i].depth = depth[idx] = stk.back().depth + 1, par[idx] = stk.back().idx;
        stk.push_back(intv[i]);
    }
    sort(intv+1, intv+l+1, cmp_index);

    /// LCA
    for(int i=1; i<=l; i++) LCADB[i][0] = par[i];
    for(int d=1; d<20; d++) for(int i=1; i<=l; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];

    /// 마지막으로 정점 높이를 구하고, 정점별 대표 구간 (해당 점을 끝점으로 가지며 가장 깊이가 낮은 최대 두 개의 구간)을 구한다
    for(int i=1; i<=n; i++) depthV[i] = 1e9;
    for(int i=1; i<=l; i++){
        depthV[intv[i].l] = min(depthV[intv[i].l], intv[i].depth);
        depthV[intv[i].r] = min(depthV[intv[i].r], intv[i].depth);
    }
    for(int i=1; i<=l; i++){
        if(intv[i].r == intv[i].l + 1) intvR[intv[i].l] = i, intvL[intv[i].r] = i;
    }
}

vector<int> vertices[200002];
int sps[200002][20][2][2]; /// sps[i][d][a][b]: i번 간선의 끝점 (a=0이면 왼쪽 끝점, a=1이면 오른쪽 끝점)에서 LCADB[i][d]번 간선의 끝점 (b=0이면 왼쪽 끝점, b=1이면 오른쪽 끝점)으로 가는 최단 거리 "코드를 무지성 복붙하기 전에 최소한 한 번 읽어는 봅시다" \
int dist(int depth, int L, int R){
    return abs(lower_bound(vertices[depth].begin(), vertices[depth].end(), L) -
               lower_bound(vertices[depth].begin(), vertices[depth].end(), R));
}

void makeSps(){
    /// Sparse table을 만들기 전에, 먼저 높이별 정점 목록 작성
    for(int i=1; i<=l; i++){
        vertices[depth[i]].push_back(intv[i].l);
        vertices[depth[i]].push_back(intv[i].r);
    }
    for(int i=1; i<=l; i++){
        sort(vertices[i].begin(), vertices[i].end());
        vertices[i].erase(unique(vertices[i].begin(), vertices[i].end()), vertices[i].end());
    }

    /// 이제 sparse table을 만든다
    for(int i=1; i<=l; i++){
        if(!par[i]) continue;
        int d = depth[i], j = par[i], ld = dist(d,intv[i].l,intv[j].l), rd=dist(d,intv[i].r,intv[j].r);
        sps[i][0][0][0] = min(ld, rd+2);
        sps[i][0][0][1] = min(ld+1, rd+1);
        sps[i][0][1][0] = min(ld+1, rd+1);
        sps[i][0][1][1] = min(ld+2, rd);
    }

    for(int d=1; d<20; d++){
        for(int i=1; i<=l; i++){
            if(LCADB[i][d] == 0) continue; /// 이런 간선이 없다
            int j = LCADB[i][d-1];
            sps[i][d][0][0] = min(sps[i][d-1][0][0]+sps[j][d-1][0][0],sps[i][d-1][0][1]+sps[j][d-1][1][0]);
            sps[i][d][0][1] = min(sps[i][d-1][0][0]+sps[j][d-1][0][1],sps[i][d-1][0][1]+sps[j][d-1][1][1]);
            sps[i][d][1][0] = min(sps[i][d-1][1][0]+sps[j][d-1][0][0],sps[i][d-1][1][1]+sps[j][d-1][1][0]);
            sps[i][d][1][1] = min(sps[i][d-1][1][0]+sps[j][d-1][0][1],sps[i][d-1][1][1]+sps[j][d-1][1][1]);
        }
    }
}

int getLCA(int x, int y){
    if(depth[x] > depth[y]) swap(x, y);
    for(int d=0; d<20; d++) if((depth[y]-depth[x])&(1<<d)) y = LCADB[y][d];
    if(x==y) return x;
    for(int d=19; d>=0; d--) if(LCADB[x][d]!=LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
    return par[x];
}

int kthParent(int x, int d){
    for(int i=0; i<20; i++) if((d>>i)&1) x = LCADB[x][i];
    return x;
}

int distUp(int x, int depth, int a, int b){
    int ans[2][2] = {0,1,1,0};

    for(int d=0; d<20; d++){
        if((depth>>d)&1){
            int tans[2][2];
            tans[0][0] = min(ans[0][0] + sps[x][d][0][0], ans[0][1] + sps[x][d][1][0]);
            tans[0][1] = min(ans[0][0] + sps[x][d][0][1], ans[0][1] + sps[x][d][1][1]);
            tans[1][0] = min(ans[1][0] + sps[x][d][0][0], ans[1][1] + sps[x][d][1][0]);
            tans[1][1] = min(ans[1][0] + sps[x][d][0][1], ans[1][1] + sps[x][d][1][1]);
            for(int a=0; a<2; a++) for(int b=0; b<2; b++) ans[a][b]=tans[a][b];
            x = LCADB[x][d];
        }
    }

    return ans[a][b];
}

void answerQuery(){
    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        if(abs(x-y) == 1){
            puts("0");
            continue;
        }
        if(x>y) swap(x, y);
        x = intvR[x], y = intvL[y];

        /// LCA 구간을 찾는다
        int p = getLCA(x, y), d = depth[p];
        int ans = INT_MAX;

        /// Case 1 시도
        if(p) ans = min(ans, distUp(x, depth[x]-d, 0, 0) + 1 + distUp(y, depth[y]-d, 1, 1));
        /// Case 2 시도
        if(depth[x] > d && depth[y] > d)
            ans = min(ans, distUp(x, depth[x]-d-1, 0, 1) + distUp(y, depth[y]-d-1, 1, 0)
                           + int(prev(upper_bound(vertices[d+1].begin(), vertices[d+1].end(), intv[kthParent(y, depth[y]-d-1)].l))
                           - lower_bound(vertices[d+1].begin(), vertices[d+1].end(), intv[kthParent(x, depth[x]-d-1)].r)));

        printf("%d\n", ans - 1);
    }
}