IOI 2018 Day 1

(2018.9.9 : 모든 문제의 풀이를 작성하였다.)

IOI 2018 Day 1 대회가 종료되었다.

한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라.

• 김세빈, 100 / 37 / 49, 21등 - 56등
• 노영훈, 100 / 37 / 49, 21등 - 56등
• 강태규, 100 / 25 / 49, 70등
• 윤교준, 100 / 5 / 49, 137등 - 144등

미국의 Benjamin Qi가 만점인 300점을 받아냄으로써 Day 1의 압도적인 1등을 차지하였다. 그 뒤를 3번 문제를 해결한 학생들이 대다수 차지하였다. 흥미로운 점은 3번 문제를 해결한 많은 학생들이 2번 문제에서 충분한 점수를 받지 못했다는 점이다. 51점과 31점 차는 느낌이 다르다. 주최측은 3번 문제를 풀었을 때 큰 이득을 취할 수 있게 배점을 준 것 같은데, 많은 학생들이 쉬운 점수를 얻지 못한 상황이라 역전의 여지가 크다. 한국 학생들에게 천운이 따랐다고 생각한다.

나는 IOI 2018 Day 1 대회에 학생 코치로 참가하면서 교수님들의 번역을 도왔고, 남는 시간 동안 문제를 풀어볼 수 있었다. 간단한 문제의 요약과, 해당 문제들의 풀이를 써 보려고 한다.

Problem 1. 콤보

Problem

${A, B, X, Y}$ 라는 4개의 문자로만 이루어진 길이 $N$의 숨겨진 문자열 $S$ 가 있다. 당신은 $S$의 길이 $N$은 알고 있으나 문자열의 내용은 알지 못한다. 당신은 숨겨진 문자열을 찾아야 하며, 이를 위해 다음 함수를 사용할 수 있다.

$query(p) : $ 문자열 $p$ 를 받고, 정수 하나를 반환한다. 이 함수는, 숨겨진 문자열 $S$의 접두사(Prefix) 중, $p$의 부분 문자열인 최장 문자열의 길이를 반환한다. $0 \leq |p| \leq 4N$ 를 만족해야 한다.

또한, $S$에는 아주 신기한 특징이 있는데, 바로 $S$의 첫번째 문자와 첫번째가 아닌 문자가 항상 다르다는 것이다.

$N \leq 2000$ 이며, 만점을 받기 위해서는 최대 $N+2$번의 쿼리만을 사용해야 한다.

Solution

아주 좋은 문제라고 생각한다. 난이도는 상당히 낮지만, 차근 차근 단계적으로 생각하면서 푸는 게 좋은 문제이다. 이 글에서도, 쉬운 풀이에서 시작해서 단계적으로 $q$를 줄여나가는 방식으로 서술한다.

$q = 2N + 1$ (30점)

최대 접두사의 길이를 알 수 있다는 것을 생각해 보면, 함수를 불렀을 때 우리가 알아낼 수 있는 정보는 문자열을 앞에서부터 얼마나 맞추었는가 이다. 우리는 고로 앞에서부터 한 글자 한 글자 넣어보면서, 맞는 글자를 순서대로 찾는 접근을 생각해 볼 수 있다.

첫번째 문자부터 맞춰보자. 이건 "A", "B", "X", "Y"를 넣어보고 1인 게 있는지 보면 된다. 그런데, "Y"는 넣어볼 필요가 없다. "A", "B", "X" 를 넣어본 후 그 중 첫번째 문자가 없다면 "Y"번 문자가 결정되기 때문이다. 고로 3번의 연산으로 맞출 수 있다.

두번째 문자 이후를 맞추는 것도 똑같은 방식으로 하면 된다. 현재 문자열에 4개의 후보를 붙여본 후 길이가 증가한 쪽을 찾아주면 된다. 그런데, 첫번째 문자와 두번째 문자 이후는 다르다. 고로 후보는 3개이다. 그러면 그 중 2개만 넣어보면 되기 때문에 각 문자당 2번의 연산으로 맞출 수 있다. $q = 3 + 2(N-1) = 2N+1$ 이다.

$q = N + 3$ (97점)

각각의 문자를 맞추는 데 2번의 연산을 사용하고 있는데, 생각해 보면 이는 상당한 낭비이다. 우리는 $query$ 함수에서, 답의 길이를 신경 쓰고 있지 않고, 단순히 그 길이가 $p$의 길이인지 아닌지만을 보고 있다. 이보다 조금 더 많은 정보를 알아볼 수 없을까?

여기서 활용할 만한 정보는, 첫번째 문자와 다른 문자들이 다르다는 정보와, $p$의 길이가 상당히 길어도 된다는 것이다 ($4N$). 첫번째 문자와 다른 문자들이 다르기 때문에, 문자열 여러개를 쌓은 후, 그들 중 최댓값을 물어볼 수 있다. 예를 들어서, 첫번째 문자를 3번의 연산으로 찾은 후, 모두 첫번째 문자로 시작하는 4개의 문자열 $S_1, S_2, S_3, S_4$ 에 대해서 $query(S_1S_2S_3S_4)$ 를 날렸다고 하자. 이 경우, 그 반환값은 $max(query(S_1), query(S_2), query(S_3), query(S_4))$ 가 된다. 첫번째 문자가 좋은 분리자(separator) 역할을 하여서 여러 개의 문자열을 동시에 처리할 수 있다.

위 관찰을 사용해서 한번의 연산으로 각 문자를 맞출 수 있을까? 첫번째 문자를 알고 있어야 위 관찰을 사용할 수 있으니, 일단 그것은 3번의 쿼리로 찾았다고 가정하자. 현재 찾은 문자열이 $S$ 이고, 남은 문자를 $p, q, r$ 라고 표현하면, 각 문자에 따라서 반환값이 다른 것이 우리의 목표이다. 그러면.. $p$ 일때는 $|S| + 2$, $q$ 일때는 $|S| + 1$, $r$ 일때는 $|S|$ 이면 참 좋을 것이다. $p$ 일때 $|S| + 2$ 가 나오길 원한다면, 뒷 글자로 가능한 모든 것들을 넣어야 max 항에서 하나라도 튀어 나올 것이다. 고로, $query(SppSpqSprSq)$ 를 보낸 후, 각 케이스에 따라서 적당히 이어 붙여 주면 된다.

… 그런데, 위 알고리즘은 마지막 문자가 코너 케이스라서, 이 경우에는 일일이 해 줘야 한다. 마지막 문자의 경우의 수는 2개이다. 고로, $q = 3 + (N-2) + 2 = N + 3$ 이다.

$q = N + 2$ (100점)

마지막 서브태스크는 첫번째 문자를 2번 안에 처리해야 풀 수 있는 문제이다. 이는 이분 탐색과 비슷한 아이디어를 사용하면 된다. 집합을 반으로 나눠서, 가능성을 하나 하나 없애는 것이 아니라 반토막내는 것이다. 첫번째 쿼리를 날릴 때 $query(AB)$ 를 해 보면, 'A', 'B' 일 때는 반환값이 1, 아닐 때는 0이 나오게 된다. 이렇게 되면, 4개의 가능성을 2개의 가능성으로 줄일 수 있으니, 그 다음에 $query(A), query(X)$ 중 원하는 것을 하면 된다. 고로, 전체 문제를 $N + 2$ 번의 쿼리로 해결할 수 있다.

Alternative Solution

위 풀이는 정해이자 이창수 조교가 찾은 풀이이고, 내가 찾은 풀이 (그리고 김세빈 학생이 대회 중 찾은 풀이) 는 약간 다르다. 나의 풀이는 한 문자를 한 번에 맞추는 대신, 두 문자를 두 번에 맞추는 형태의 풀이이다.

맨 처음 $query(SppSpqSqp)$ 를 날린다. 이 경우 뒷 글자가 $r$ 이면 결과가 $|S|$이다. 그렇지 않고, 결과가 $|S|+2$ 라고 하자. 이 때는 $query(Spq)$ 를 날려주면, 이 결과에 따라서 뒷 두 문자가 $pp, pq, qp$ 인지 알 수 있다. $|S| + 1$ 의 경우는 대칭적이다.

이 풀이는 한 문자를 맞췄다면 쿼리를 하나만 사용하고, 두 문자를 맞췄다면 쿼리를 두 개 사용한다. 첫 문자와 마지막 문자는 위와 같이 케이스 처리를 해 주면 된다. (입력의 마지막 문자에 대한 케이스 처리는 필요하지 않을 수도 있다.) 이 풀이는 문자열의 길이가 $3N$ 이하여도 문제를 해결할 수 있다.

나의 소스 코드 (Alternative Solution을 구현했다.)

Problem 2. 자리배정

Problem

$H \times W$ 그리드에 $[0, HW-1]$ 사이의 서로 다른 정수들이 적혀있다. 당신은 위 연산을 온라인 으로 지원하는 프로그램을 설계해야 한다.

• 그리드의 두 셀이 주어졌을 때, 두 셀에 적힌 정수를 스왑한다. 그 후, $1 \leq k \leq HW$ 인 정수 $k$ 중, 0 이상 $k-1$ 이하인 정수들이 적힌 셀들의 위치를 모았을 때, 이들이 직사각형을 이루는 $k$ 의 개수를 반환하라.

직사각형을 이룬다는 것은, 정수 $r_1, c_1, r_2, c_2$ 가 존재하여서, 셀들의 위치들의 집합과 $\{(x ,y)|x \in [r_1, r_2], y \in [c_1, c_2]\}$ 가 동일함을 의미한다.

제한은, 총 연산의 횟수를 $Q$ 라고 할 때, $Q \leq 50000, HW \leq 1000000$ 이다.

Solution

$O(HWQ)$ (11점)

일단 어떠한 셀의 집합이 직사각형 인지를 판별하는 방법부터 찾아보자. 가장 명료한 방법은 그냥 적혀있는 정의를 따라서 박스를 쳐 주고, 박스 안에 있는 원소들이 셀의 집합과 일치하는지 보는 것이다. $r_1 = min_{i < k}(r_i), r_2 = max_{i<k}(r_i), c_1 = min_{i < k}(c_i), c_2 = max_{i < k}(c_i)$ 라고 두면 현재 셀을 전부 덮는 적당한 직사각형을 찾을 수 있다. 이 직사각형이랑 주어진 집합이 일치하는 지 보려면, 그냥 크기 (넓이?) 를 세어서 같은지 보면 된다. 즉, $(r_2 - r_1 + 1)(c_2 - c_1 + 1) = k$ 이면 답이고, 아니면 답이 아니다.

이제 원래 문제로 돌아가 보자. 각 쿼리를 개별적으로 생각한다. 스왑은 대충 하면 $O(1)$이다. $k$의 개수를 세는 것은, $k$ 를 1에서 $HW$까지 증가시켜나가면서 그 순간의 $r_1, r_2, c_1, c_2$ 를 관리하면 셀 수 있다. 고로, $O(HW)$ 이다. 쿼리당 $O(HWQ)$ 에 문제를 해결하여서 11점을 받는다.

$|a - b| \leq 10000$ (17점)

이 방법을 서브태스크 4로 확장시키는 것은 어렵지 않다. 관찰은, $swap(a, b)$ 가 호출되었다고 할 때 ($a < b$), $0$ 이상 $k-1$ 이하인 정수들이 적힌 셀들의 위치를 모은 집합은, $a < k \leq b$ 일 때만 변화가 있다. $k \leq a$ 일 때는 집합에 바뀐 원소가 둘 다 없고, 그 후에는 바뀐 원소가 둘 다 있기 때문이다. 고로, 이 구간 사이에 있는 $k$ 에 대해서만, 그에 대응되는 직사각형 ($(r_1, r_2, c_1, c_2)$ 쌍) 이 변화가 있다. 이 부분에 대해서 직사각형을 다시 계산해 주고, 해당 $k$가 답이 되는 지의 여부도 그에 따라 구해준다. $O(Qmax(|a - b|))$ 에 문제가 해결 된다.

$O(HW + Q(H + W))$ (37점)

37점 풀이까지도 지금까지의 생각에 기반해서 어렵지 않게 끌어낼 수 있다. 관찰은, 직사각형이 바뀔 수 있는 지점이 많아야 $H + W$ 개 정도라는 것이다. 이는, $k = 1$일 때의 직사각형의 높이와 너비가 1이고, $k = HW$일 때의 직사각형의 높이와 너비가 $H, W$ 이며, 직사각형이 바뀌는 순간에는 높이 혹은 너비가 1 이상 증가하기 때문이다. 한 직사각형에 대해서 답이 되는 $k$ 가 하나로 고정되기 때문에, 전체 직사각형의 변화를 $O(H+W)$에 시뮬레이션하면 문제를 해결할 수 있다.

현재의 직사각형이 있을 때, 이 다음에 등장하는 직사각형을 어떻게 찾을까? 현재의 직사각형이 포함하지 않는 가장 작은 숫자가, 이 직사각형의 크기를 바꾸는 숫자가 될 것이다. 우리는 현재의 직사각형이 포함하지 않는 가장 작은 숫자를, 빠른 시간 안에 찾아야 한다.

직사각형 안에 점이 있다 ($r_1 \leq x \leq r_2, c_1 \leq y \leq c_2$) 는 식을 뒤집으면, 우리가 찾는 것은 $x < r_1, x > r_2, y < c_1, y > c_2$ 중 하나를 만족하는 점 $(x, y)$ 중 적힌 값이 최소인 점이다. 조건이 OR의 형태이니, 각각의 문제를 따로 해결할 수 있다. 각 $x$ 에 대해서 그 줄에 있는 가장 작은 수를 $Xmin[x]$, 각 $y$에 대해서 그 줄에 있는 가장 작은 수를 $Ymin[y]$ 라고 하자. 우리는 $Xmin, Ymin$ 의 prefix / suffix 중 최솟값을 찾는 문제이다. 이는 단순히 prefix minimum / suffix minimum을 전처리로 $O(H+W)$에 취해주면 찾을 수 있다. 고로, 다음 직사각형의 형태와 이것이 등장하는 순간을 모두 찾을 수 있으니, 한 직사각형에 대해서 답이 되는 $k$가 올바른지를 판별할 수 있다.

$Xmin, Ymin$은 초기에 선형 시간에 전처리할 수 있고, swap 쿼리가 들어올 때 각 배열에서 최대 2개의 값만 갱신하면 된다. 고로 $O(HW) + O(Q(H + W))$ 에 관리할 수 있다.

$O(HW + Q\log(HW))$ (100점)

$O(Q(H + W))$ 면 문제를 거의 다 풀었지 않았을까..? 라고 생각할 수 있으나, $H = 1$ 인 서브태스크를 열심히 풀다 보면, 지금까지 했던 관찰이 충분하지 않다는 것을 알 수 있다. $max / min$ 과 같은 수식에 의존해서 생각할 수도 있으나, 이 방법으로는 $H = 1$일 때도 좋은 답이 나오지 않는다. 발상의 전환이 필요한 순간이다.

생각해야 할 것은 직사각형의 기하학적 성질이다. 임의의 $k$에 대해서 $[0, k-1]$ 까지의 수가 색칠된 그리드를 생각해 보자. 색칠된 모든 셀이 직사각형을 이룬다는 것은 무엇일까? 하나의 컴포넌트를 이루고, 해당 컴포넌트에 볼록하게 꺾이는 직각이 4개 있고, 오목하게 꺾이는 직각은 없고... 직사각형의 판별을 직각의 개수 에 대한 이야기로 환원할 수 있다는 희망이 보인다.

이 부분을 조금 더 명확히 해 보자. 4방향으로 연결된 점들의 컴포넌트를 "다각형" 이라고 정의하자. 현재 색칠된 셀들이 직사각형을 이룬다는 것은

• 다각형이 하나고
• 이 다각형에 볼록한 각이 4개이고, 오목한 각이 0개이며
• 다각형 내부에 구멍이 없다

는 것과 동치이다. 한편, 구멍이 있다면 오목한 각이 4개 이상 존재하며, 다각형이 2개 이상이면 볼록한 각이 8개 이상이다. 고로, 이 모든 조건은 전체 그리드에 볼록한 각이 4개이고, 오목한 각이 0개이다 라는 것과 동치이다. 즉, 직사각형의 판별은, 볼록한 각과 오목한 각의 개수를 세는 문제로 환원된다. 그리고 이를 모든 $k$에 대해서 세는 것은, 각 $k$에 대해서 볼록한 각과 오목한 각의 개수를 관리한 후, 이 쌍이 $(4, 0)$인 $k$의 개수를 세는 것과 동일하다.

직각의 개수를 관리할 때는, 각 셀의 모서리를 기준으로 생각해 보자. 어떠한 모서리가 직각을 이루는 지 아닌지는, 해당 모서리의 사방에 있는 4개의 셀이 언제 색칠되는 지에 종속적이다. 정확히 분석하자면, 다음과 같다.

• 4개 중 1개의 셀이 칠해져 있다면 볼록한 각이 1개이다.
• 4개 중 2개의 셀이 칠해져 있다면 볼록한 각이 2개거나 0개이다. (셀이 마주보면 2개, 붙어 있으면 0개)
• 4개 중 3개의 셀이 칠해져 있다면 오목한 각이 1개이다.

결국 위 조건은 연속된 구간에 있는 $k$에 대해서 성립하니, 어떠한 $k$의 구간에 대해서 해당 모서리가 몇 개의 직각을 이루게 되는 지를 알 수 있다. 전체의 볼록 / 오목 직각의 개수는 이 정보들을 모두 합하면 알 수 있고, 쿼리로 어떠한 위치의 값이 바뀐다면 대응되는 8개의 모서리에 대해서 값을 다시 설정해 주면 된다.

이는 구간 쿼리 문제로 해석될 수 있다. 초기 initialization과 쿼리의 swap 과정에서 구간에 일정한 수의 오목 / 볼록 각의 개수를 더해주고, 전체 구간에서 볼록한 각과 오목한 각이 각각 $4, 0$개 있는 원소들의 개수를 세어 주는 것이다. 구간 쿼리에서 일정한 수의 개수를 세는 것은 일반적으로 쉽지 않지만, 이 문제에는 약간의 트릭이 있다 : 다각형이 하나 이상 있다면, 오목한 각은 무조건 4개 이상 존재한다. 고로, $(4, 0)$ 의 개수를 세는 것이 아니라. 최솟값과 최솟값의 등장 횟수를 센 이후, 그 최솟값이 $(4, 0)$ 쌍과 일치하는 지 보면 된다. 모두 일반적인 pair 비교와 같이 (볼록한 각 개수, 오목한 각 개수)를 lexicographic하게 비교하면 된다. 구간 덧셈, 전체 최솟값, 전체 최솟값 개수를 세는 자료 구조는 Lazy propagation을 사용한 Segment Tree를 사용하면 쉽게 구현할 수 있다.

마지막으로, 하나의 Lazy propagation 연산은 빠른 편이 아니기 때문에, 초기 initialization을 할 때 Lazy propagation을 사용하기 보다는 변홧값 배열 등으로 전처리를 해 놓은 후 세그먼트 트리를 선형 시간에 초기화하는 것이 좋다. 이 경우 시간 복잡도가 $O((Q + HW)\log (HW))$ 에서 $O(HW + Q\log (HW))$ 로 줄어든다. 나의 경우에는 상당히 최적화된 코드를 구현하여서 $O(HW\log (HW))$ 로 통과하였으나, 일반적으로는 위 최적화가 필수적이다. 또한, 각 쿼리가 최대 50번의 Lazy propagation을 요구할 수 있기 때문에, $Q \leq 50000$ 으로 제한이 꽤 널널함에도 불구하고 추가적인 상수 최적화가 더 필요할 수 있다.

나의 소스 코드 ($O((Q + HW)\log(HW))$)

Problem 3. 늑대인간

Problem

$N$ 개의 도시와 $M$개의 도로로 이루어진 양방향 그래프가 있다. 각 도시에는 $0, 1, ..., N-1$ 까지의 서로 다른 번호가 부여되어 있는데, 각 도시의 인구 수에 비례해서 매겨진 번호들이다.

$Q$개의 질의가 들어온다. 각 질의는 $S, E, L, R$ 로 표현된다. 당신은 다음과 같은 경로의 존재 여부를 YES / NO로 판별하여야 한다.

• 경로는 $S$에서 시작하여, 당신이 고른 정점 $v$를 거치고, $E$에서 끝난다. $v = S, v = E$ 여도 된다.
• $S$ 에서 $v$ 로 가는 경로 상에는 번호가 $L$ 미만인 정점이 없으며, $v$ 에서 $E$ 로 가는 경로 상에 번호가 $R$ 초과인 정점이 없다. 이 조건은 경로의 끝점에도 적용된다. 예를 들어, $v$는 $L \leq v \leq E$ 를 만족해야 한다.

질의는 하나의 함수로 각각 주어지는 것이 아니고, 한꺼번에 주어진다. 즉, 오프라인 풀이가 가능하다.

제한은, $N \leq 200000, M \leq 400000, Q \leq 200000$ 이다.

Solution

$O((N + M)NQ)$ (7점)

문제를 풀기 위해서 우리는 적당한 $v$ 를 골라야 하고, 또한 이 $v$ 에 대해서 경로를 찾을 수 있는지 역시 판별해야 한다. 제한이 굉장히 작으니, 이를 모두 가장 단순한 방법으로 처리해 보면 된다.

각각의 쿼리에 대해서, 모든 $L \leq v \leq R$ 을 다 시도해 본다. $v$ 를 거쳐서 $S$에서 $E$로 가는 풀이가 있다는 것은, $S$에서 $v$로 $L$ 이상의 정점만을 거쳐서 가는 경로가 있고, $v$에서 $E$로 $R$ 이하 정점만을 거쳐서 가는 경로가 있는지 확인한다. 이는 그래프 탐색 알고리즘을 사용하여서 간단하게 해결할 수 있다. 총 $NQ$ 번의 그래프 탐색을 하게 되니, 시간 복잡도는 $O((N+M)NQ)$ 이다.

$O((N + M)Q)$ (15점)

여전히 제한이 작은 편이나, 조금 더 효율적인 방법을 생각해야 하는 서브태스크이다. 지금 가장 비효율적인 부분은 $v$ 를 찾지 못해서 모든 $v$를 다 순회하는 것이다. 이를 조금 더 간단하게 해 보자.

$v$를 고정시키지 말고, 고정된 값인 $S, E$에 기반해서 생각해 보자. $v$ 로 가능한 후보는 $S$에서 $L$ 이상의 정점만을 거쳐 갈 수 있으며, $E$에서 $R$ 이하의 정점만을 거쳐 갈 수 있는 정점들이다. 이 두 집합을 그래프 탐색 알고리즘으로 구한 후, 두 집합의 교집합이 존재하는 지 판별하면 된다. 존재하면 그 집합에 있는 어떤 원소도 $v$가 될 수 있으며, 존재하지 않으면 답은 NO이다. 이 경우 그래프 탐색은 쿼리당 2번으로 충분하다. 고로 시간 복잡도는 $O((N+M)Q)$ 이다.

주어진 그래프가 직선 (49점)

이 서브태스크에서 주어진 그래프는 직선이다. 직선에서 $S$에서 $L$ 이상의 정점만을 거쳐 갈 수 있는 정점들, $E$에서 $R$ 이상의 정점만을 거쳐 갈 수 있는 정점들은 구간 을 이룬다. 즉, $S$에서 도달할 수 있는 직선 상 가장 왼쪽 정점과 오른쪽 정점을 구하면 그 사이는 전부 도달할 수 있으며, $E$에 대해서도 이 성질이 동일하다는 것이다. 도달할 수 있는 정점이 구간 을 이루면, 집합을 표현할 때 두 개의 정수 (시작점, 끝점) 만 있으면 충분하며, 두 집합이 교집합을 이루는 지도 쉽게 계산할 수 있다. 위의 경우에는 집합이 마음대로 구성될 수 있어서 비효율적인 알고리즘이 필요했지만, 그래프가 직선이 되면서 이에 대한 자유도가 생긴 것이다.

고로, 문제는 $S$에서 $L$ 이상의 정점만을 거쳐 갈 수 있는 정점의 구간이 무엇인지를 구하는 것이다. (반대는 동일하게 하면 된다.) 크게 두 가지 방법이 있다.

• 자료 구조. Sparse Table이라는 자료 구조를 사용하면, 각각의 위치에서, $L$ 이상의 정점만을 거쳐 얼마나 오른쪽으로, 얼마나 왼쪽으로 갈 수 있는지를 쉽게 $O(\log N)$ 에 계산할 수 있다. 이 자료구조에 대한 설명은 생략한다. 시간 복잡도는 $O(Q\log N)$ 이다.
• 쿼리 정렬. 쿼리가 오프라인이라는 점을 사용해서 다른 형태의 풀이를 사용할 수도 있다. 쿼리로 주어지는 $(S, L)$ 쌍을 $L$이 감소하는 순서대로 정렬해 보자. $L$ 이 감소할수록 거쳐갈 수 있는 정점의 개수가 많아지니, 컴포넌트가 커진다는 것을 알 수 있다. 이제 컴포넌트를 서로소 집합 (Union-Find) 를 통해서 관리해 줄 수 있다. 각 구간의 시작점 / 끝점은, 해당 컴포넌트에서 가장 왼쪽에 있는 정점과 오른쪽에 있는 정점을 추가적으로 저장해 주면 알아낼 수 있다.

$O((N+M+Q)\log N)$ (100점)

주어진 그래프가 직선일 때는, $S$에서 $L$ 이상의 정점만을 거쳐서 갈 수 있는 정점의 집합을 직선 상의 구간으로 나타낼 수 있었기 때문에, 그러한 집합의 계산 및 교집합 판별을 모두 효율적으로 할 수 있었다. 하지만 이제 문제는 다시 일반 그래프로 돌아왔기 때문에, 위와 같은 접근법을 그대로 사용할 수 없다.

먼저, 그러한 집합의 "계산"을 어떻게 하는지 알아보자. 그래프의 컴포넌트를 관리할 수 있는 가장 좋은 방법은 Union-Find이다. 49점 풀이의 "쿼리 정렬" 에서 사용한 아이디어를 활용하면, 결국에 $L$을 감소시키면서 간선을 추가하고, 현재 $S$와 같은 집합의 원소들을 구해주면 되기 때문이다.

이렇게 하면 집합을 특정한 자료구조에 저장해 놓을 수는 있으나, 그 원소가 무엇인지를 잘 알아내는 방법은 명확하지 않다. 그 실마리를 찾아보기 위해서 Union-Find의 작동 과정을 다시 돌아보자. 초기에는 $\{0\}, \{1\}, \{2\}, \cdots, \{n-1\}$ 과 같은 크기 1의 컴포넌트들이 여러 개 있다. Union-Find는, 서로 다른 두 서로소 집합이 있다면, 이 두 집합을 받아서, 두 집합의 합집합을 반환한다. 최후에는, 크기 $n$의 컴포넌트가 단 하나 존재한다. 이 과정에서 나온 서로 다른 집합은 정확히 $2n-1$ 개이며, 후반에 나온 $n-1$ 개의 집합은, 두 집합의 합집합이라는 관계를 가진다.

Union-Find에서 나온 서로 다른 $2n-1$개의 컴포넌트를 하나의 정점으로 보자. 두 개의 컴포넌트가 하나의 컴포넌트로 합쳐지는 관계를 가지는데, 우리는 이를 이진 트리 의 형태로 모델링해 볼 수 있다. 어떠한 컴포넌트가 크기 1이면 자식이 없고 (리프), 크기 2 이상이면 이 컴포넌트가 합쳐준 두 컴포넌트를 자식으로 가지는 것이다. 이제, 쿼리로 주어지는 $(S, L)$ 쌍은 트리 상의 정점에 대응되며, 어떠한 정점 컴포넌트의 원소는 해당 컴포넌트의 서브트리 안에 있는 리프들 이다. 서브트리는 오일러 투어의 형태로 나타낼 경우 구간 으로 표현할 수 있음이 아주 잘 알려져 있다. 오.. 오옷!!! 주모!!! 여기 오일러뽕 한사발 주소!!! 이 부분에 대해서 자세한 설명은 생략한다.

위 문단을 읽으면서 모두가 흥분했겠지만, 일단 잠시 멈추고, 아무튼 $(E, R)$ 쌍에 대해서 똑같은 과정을 반복해서 또 다른 트리를 만든다. 그러면 트리 $T_1, T_2$ 가 나온다. 우리가 푸는 문제는 다음과 같이 변환된다.

• $[0, n-1]$ 사이의 서로 다른 번호를 가진 $n$ 개의 리프를 가지는 두 트리 $T_1, T_2$ 가 주어진다. 쿼리로 두 정점 $v \in V(T_1), w \in V(T_2)$ 가 주어질 때, $T_1$ 에서 $v$의 서브트리에도 있고, $T_2$ 에서 $w$의 서브트리에도 있는 정점이 존재하는지를 판별하여라.

$T_1$ 에서 오일러 투어 상 리프 순서를 $P_1$, $T_2$ 에서는 $P_2$ 라 하자. 그러면,

• 두 순열 $P_1, P_2$ 와, 구간 $[x_1, x_2]$, $[y_1, y_2]$ 가 주어질 때, $P_1$에서의 위치가 $[x_1, x_2]$ 사이이고, $P_2$에서의 위치가 $[y_1, y_2]$ 사이인 숫자 $x$ 가 존재하는지를 판별하여라.

$x$ 의 $P_1$ 상 위치를 $P_1^{-1}(x)$, $P_2$ 상 위치를 $P_2^{-1}(x)$ 라 하면

• 구간 $[x_1, x_2]$, $[y_1, y_2]$ 가 주어질 때, $x_1 \leq P_1^{-1}(x) \leq x_2$, $y_1 \leq P_2^{-1}(x) \leq y_2$ 를 만족하는 점 $x$ 가 존재하는지 판별하여라.

$(P_1^{-1}(x), P_2^{-1}(x))$ 를 좌표평면에 찍으면, 이는 $N$개의 점이 있을 때, 주어진 직사각형 안에 점이 한 개 이상 있는지를 판별하는 문제가 된다. 잘 알려진 형태의 문제지만, 간단하게 풀이를 소개한다. $y$ 축을 key로 가지는 최댓값 segment tree를 만들고, 쿼리를 $x_2$ 순으로 정렬한다. $x \leq x_2$ 를 만족하는 모든 점 $(x, y)$ 에 대해서, $y$ 위치에 $x$ 라는 값을 덮어준다. 이제, $[y_1, y_2]$ 에 대한 구간 쿼리의 결과가 $x_1$ 이상이면, 답이 존재하고, 그렇지 않으면 답이 존재하지 않는다.

나의 소스 코드