2022.12.18 problem solving

BOJ 26410. Intersection of Tangents

답은 $(min(x_i), min(y_i))$ 입니다. 이 점에서는 $x$ 축에 평행한 접선과 $y$ 축에 평행한 접선을 그을 수 있습니다.

자명하다고 볼 수도 있고, 이런 저런 복잡한 접근이 정수 점을 잘 못 찾는다는 점에서 착안할 수도 있겠습니다.

BOJ 26408. Game

쿼리당 $O(n)$

먼저, 최적 전략에서 캐릭터는 최대 한번 이동함을 관찰할 수 있습니다. 어떠한 시나리오에서 두 명 이상이 이동을 선택했다고 합시다. 전략에 의해 마지막으로 이동을 선택한 사람이 그 게임의 승자가 됩니다. 그 경우, 그 전에 이동을 선택한 사람은 본인이 결론적으로 게임을 짐에도 불구하고 이동을 선택했기 때문에 가정에 모순입니다.

두 번째로, 승자는 $a_i = i$ 혹은 $i = 0$ 을 만족함을 알 수 있습니다. 캐릭터가 아예 이동하지 않으면 $i = 0$ 이 승자가 됩니다. 그 외 경우 캐릭터는 항상 한 번 이동하는데, $a_i = i$ 를 만족하는 경우에만 한번의 이동으로 자신의 승리를 보장할 수 있습니다. 다만, $a_i = i$ 라고 무조건 승리를 하게 되는 것은 아닙니다. 그 전에 다른 캐릭터가 본인의 승리를 직감하고 다른 곳으로 이동하거나, 그 이후 다른 캐릭터가 한 번의 이동으로 본인의 위치에 캐릭터를 두면 전략이 무너지기 때문입니다.

이제 $i$ 번째 사람이 승리할 조건에 대해서 구체적으로 생각해 봅시다. $i$ 번째 사람이 승리하기 위해서는, 일단 자기 턴에 캐릭터가 자기 위치에 있어야 하고 ($i = 0$ 혹은 $a_i = i$), 그 이후 사람들이 한번 이동해서 자신의 위치로 캐릭터를 두고 이길 수 없어야 합니다. 두 번째 조건만 보면, $j > i$ 중 $j - a_j = i$ 이며 승리할 수 있는 사람이 있으면 안 된다는 조건으로 해석할 수 있습니다. $win[i]$ 를 $a_i = i$ 가 자기 턴에 성립할 시 승리할 수 있을 경우 yes, 아닐 경우 no라고 한다면

• $j > i$ 중 $j - a_j = i, win[j]$ 인 사람이 있으면 $win[i] = no$
• 그 외 $win[i] = yes$

이제 자기 턴에 캐릭터가 자기 위치에 있어야 하는데, $win[i]$ 가 참이면서 $i = 0, a_i = i$ 인 최소의 $i$ 가 답이 됩니다. 저러한 $i$가 없을 수는 없습니다. 이 DP는 $i$ 를 감소시켜나가면서, 이길 수 없는 위치 $j - a_j$ 를 배열에 체크하는 식으로 판별 가능합니다.

쿼리당 $O(\log n)$

$j - a_j$ 를 $j$ 번 부모의 조상이라고 하면, 위 문제는 포레스트에서 하는 DP로 생각할 수 있습니다. 동적 계획법을 최적화하는 9가지 방법 (4/4) 의 Dynamic Tree DP 원리를 적용하여, Link-Cut Tree나 Top Tree로 트리 DP를 관리하면 됩니다.

BOJ 26413. Lysergic Acid Diethylamine

지문에도 나와 있다시피 $m = 1$ 일 경우는 풀 수가 없습니다. 이 경우는 $-1$ 로 넘어가고, $m > 1$ 을 가정합니다.

제한이 참으로 애매해서 $s_k(x)$ 를 구할 수 있을 것도 같지만, 일단 구해서 푸는 풀이로 아는 건 없습니다.

함수를 한번 풀어서 써 보겠습니다.

• $s_0(x) = x$
• $s_1(x) = f(x) + 1$
• $s_2(x) = f(f(x) + 2) + 1$
• $s_3(x) = f(f(f(x) + 3) + 2) + 1$
• $\ldots$

$k = 0$ 인 경우를 제외하면 (이 경우는 자명하니 따로 처리해 줍시다), $s_k(x)$의 반환 값은 어떠한 정수 $t$ 에 대해 $f(t) + 1 = \frac{t(t+1)}{2} + 1$ 꼴로 나옵니다. 아이디어는, 모든 $t$에 대해 $f(t) + 1$ 이 _가질 수 없는 값_이 존재한다면, 이 값을 답으로 할 경우 입력으로 주어진 $x$ 와 무관하게 항상 오답을 출력할 수 있다는 것입니다. 또한, $f(t) = f(t + 2m)$ 이기 때문에 ($f(t) = f(t + m)$ 은 아닐 수 있습니다), $0 \le t \le 2m - 1$ 에 대해서 전부 해보면 이 값이 무엇인지를 $O(m)$ 시간에 쉽게 계산할 수 있습니다. 이 과정에서 등장하지 않는 수가 없다면, $-1$ 을 출력해 줍시다. 이 알고리즘을 구현하면, 정답을 받을 수 있습니다.

이제 왜 위 알고리즘이 올바른지를 알아봅시다. $m$ 이 홀수일 경우, $f(t) = f(t + m)$ 이며, $x(x + 1) / 2 = 0$ 은 $x = m - 1, x = 0$ 에서 $0$ 이라는 동일한 값을 가집니다. 서로 다른 입력이 $m$ 개이고 그 중 두 개가 중복되니, $f$에는 빈 값이 존재할 수 밖에 없습니다. 같은 이유로, $m$ 이 홀수 소인수를 가진다면, 해당 소인수로 나눈 나머지에서 빈 값이 존재합니다. 그래서 $m$ 이 홀수 소인수가 없을 때만 위 알고리즘이 틀릴 가능성이 존재하는데, 그러한 경우 $m = 2^i$ 꼴로 표현이 가능하고, 문제 제약 조건에서 이러한 숫자는 $m = 1$ 을 포함 14개입니다.

$m$ 이 홀수 소인수일 경우 $1/2$의 확률로 어떤 수가 $f(t)$ 의 치역에 없어서, 소인수 분해 후 Tonelli-Shanks를 적용하면 $\tilde{O}(m^{1/4})$ 에도 풀릴 듯 합니다.

BOJ 26415. Ghost

문제에서 주어진 특수한 형태의 그래프에 대해, Width가 $3$ 인 Tree decomposition을 구하는 문제입니다. (Tree decomposition의 개념을 모르는 학생들이 이 문제를 풀면서 익히라는 의도로 출제하였습니다. 고로 Tree decomposition을 미리 알아야 풀 수 있는 문제는 아닙니다.)

편의상 "새로운 트리" 를 skeleton tree, 혁명적 집합을 bag 라고 부릅시다. 또한 입력이 이진 트리라고 가정합니다. 구조가 복잡하니 먼저 간단한 예시인 트리에서 문제를 해결해 보고 조금씩 일반화 합시다. 트리에서는, skeleton tree로는 원래 그래프를 그냥 쓰고, 각 노드의 bag에 해당 노드와, 해당 노드의 부모 (존재한다면) 를 그냥 담아주면 됩니다. 이 경우 모든 간선을 포함하는 bag이 존재하고, 각 노드가 이루는 서브트리가 해당 노드와 그 자식이 되니 올바릅니다. 각 bag의 크기는 2입니다.

이제 이 트리에 두 리프 $u, v$를 잇는 간선 하나를 추가해 봅시다. skeleton tree가 바뀌면 너무 머리아프니 트리는 그대로 두겠습니다. $u, v$ 를 잇는 공통 bag가 없는 것이 문제이니, 트리 상에서 $u, v$ 를 잇는 경로에 $u$ 혹은 $v$ 를 전부 추가해 주면 됩니다. 이렇게 되면 각 bag의 크기는 3이 됩니다. 모든 외곽 순환 도로 간선에 대해서 이를 똑같이 반복해 주면 - 다시 말해, $v_i, v_{i + 1}$ 사이에 $v_i$ 를 전부 추가해 주면 - 각 Bag에 최대 3개의 노드가 추가됩니다. 각 정점의 차수가 최대 3이고, 평면 상에서 각 인접한 간선 사이의 빈 공간을 뚫고 지나가면 정확히 하나의 외곽 순환 도로 간선과 교차하며, 이 간선에서 추가한 노드가 정확히 이 정점에 추가된 노드이기 때문입니다. 이 접근을 통해서 16점을 얻을 수 있습니다.

이제 5개를 4개로 줄이는 방법을 알아봅시다. 핵심 아이디어는, 트리 에지를 표현하는 bag와 외곽순환도로를 표현하는 bag를 분리하는 것입니다. 위 접근을 조금 정리해서 다음과 같은 재귀 함수를 정의합시다:

• $dfs(v)$: $v$ 의 서브트리에 대한 tree decomposition을 계산하고, 서브트리를 왼쪽 / 오른쪽으로 빠져나가는 외곽순환도로가 각각 $(v_a, v_{a+1}), (v_b, v_{b+1})$ 이면, $(v_a, v, v_b)$ 을 bag으로 가지는 노드를 루트로 한 skeleton tree를 반환.

어떠한 노드 $v$ 의 자식 $(w_1, w_2)$ 에 대해서, $dfs(w_1), dfs(w_2)$ 를 호출하면, $dfs(w_1) = (v_a, w_1, v_b)$, $dfs(w_2) = (v_b, w_2, v_c)$ 의 형태일 것입니다. 다음과 같이 합쳐줄 수 있습니다:

• $dfs(w_1) = (v_a, w_1, v_b)$ 에 대해, 새 부모로 $(v_a, w_1, v, v_b)$, $(v_a, v, v_b)$ 를 연결해 줘서 간선 $(v, w_1)$ 을 표현.
• 이제 합쳐 줄 두 bag이 $(v, v_b)$ 를 공통 원소로 가지고 있으니, 새로운 루트 $(v_a, v, v_b, v_c)$ 를 설정해 주고, 기존 루트 둘을 새로운 루트의 자식으로 둠.
• $v_b$ 가 연결 컴포넌트를 이루니 더 이상 필요없음, 새로운 루트 $(v_a, v, v_c)$ 를 설정해 주고, 기존 루트를 새로운 루트의 자식으로 둔 후 반환.

이 알고리즘은 두 노드를 합치는 데 $2$ 개의 추가적인 노드를 만들고, 각 노드를 부모로 올릴 때 $2$ 개의 추가적인 노드를 만들기 때문에 정점을 최대 $4n$ 개 가지는 skeleton tree를 반환합니다. 마지막으로, 자식이 $2$개 이상일 경우 그냥 아무 두개나 골라서 위와 같이 합쳐주는 것을 반복하면 되기 때문에, 그대로 구현하면 이진 트리 조건이 없어도 만점을 받을 수 있습니다.

BOJ 26409. Hidden Pool

일단 $t_i$ 는 정렬하고 시작합니다. 답에 대한 이분 탐색으로, $f$ 명 이상이 항상 게임에 잡히게 하는 전략의 존재성을 판별하는 결정 문제로 변환합시다. 이 전략은 $h = p - 1 - f$ 명 이하의 일반인만 큐에 잡히게 하는 전략이기도 합니다.

$d$ 가 아주 커서 절대 방송으로 정보를 얻을 수 없는 경우를 생각해 봅시다. 강찬밥이 큐를 잡을 수 있는 시점은 $0T, 1T, 2T, \ldots$ 와 같이 $kT$ 의 꼴을 이룹니다. $k = 0$ 인 시점부터 차근차근 팬들을 배치해서 모든 큐에 $f$ 명 이상의 팬이 있도록 합시다. $k = 0$ 일 때는 $h + 1$ 번째 일반인이 들어오기 직전에 $f$ 명의 팬을 한꺼번에 배치하는 방법으로 큐를 채울 수 있습니다. 이 경우 $k \le a_{h + 1}/T$ 인 경우에 큐를 잡는다면, 무조건 $f$ 명의 팬과 함께 게임을 하게 됩니다.

그 다음 $k$ 를 볼 때 달라지는 점은, 큐에 이미 몇명의 일반인이 있을 수도 있다는 것입니다. 만약에 큐에 이미 있는 일반인이 $h$명 이하라면, 크게 달라지는 것은 없고, 일반인이 $h+1$ 명이 되기 직전에 팬들을 투입하면 됩니다. $h$ 명 초과일 경우가 문제인데, 이 경우는 강찬밥이 큐에 들어가기 직전에 이 게임을 망쳐서 강찬밥이 그 다음 게임을 하게 해야 합니다. 즉, 큐에 지금 $q$ 명의 일반인이 있다면, $p - q$ 명의 팬을 $kT - 0.5$ 초에 배치해서 게임 하나를 없애야 합니다. 이를 모든 $k$ 에 대해 반복한 후, 배치한 팬의 수가 $m$ 명 이하이면 전략이 있다고 판별해 주면 됩니다.

이제 일반적인 경우를 해결해 봅시다. 만약 방송을 볼 수 있다면, 강찬밥이 $kT + d$ 시간에 큐에 들어갔음이 확인된 경우, 지금까지 남은 모든 팬들을 그 즉시 $kT + d + 0.5$ 시간에 배정해 주는 것이 최적입니다. 위에서 고안한 전략은 팬들을 가능한 최대한 늦은 시간에 배정하도록 구성되어 있으니, 큰 틀을 바꾸지 않아도 일반적인 경우를 해결할 수 있습니다.

팬을 투입하는 시간을 $T$ 로 나눈 나머지가 $d$ 미만이라면, 이 경우에는 방송을 통해서 전략적 이득을 볼 수 없고 그대로 배치해야 합니다. 반면 $d$ 초과인 경우에는, 그 시간에 팬을 꼭 투입할 필요가 없고, 방송을 본 이후에 투입을 결정해도 무방합니다. 고로

• 강찬밥이 예상과 같이 방송에 들어왔다면 뒤에 있는 팬을 끌어서 써도 무방합니다. (Event X라고 부릅니다.)
• 강찬밥이 방송에 들어오지 않았다면, 강찬밥이 다음 턴에 큐에 들어갔을 때 $h + 1$ 명 이상의 일반인과 게임을 할 수도 있습니다. 고로 $xT - 0.5$ 초가 되었을 때 해당 큐에 $h$ 명 초과의 일반인이 있다면 팬을 적절히 투입해서 해당 큐를 채워줘야 합니다. 그 다음부터는 기존과 동일합니다.

주의해야 할 것은 뒤에 있는 팬들의 수가 $f$ 명이 되지 않아서 방송을 본 이후에 투입할 팬이 부족한 경우입니다. Event X가 일어난 마지막 시점 이후 배정한 팬의 수를 관리하고, 이 팬의 수가 $f$ 에 미달하면 $10^{100}$ 시간에 미달한 만큼의 팬을 더 배정해 주면 됩니다. 앞서와 동일하게, 이를 모든 $k$ 에 대해 반복한 후, 배치한 팬의 수가 $m$ 명 이하이면 전략이 있다고 판별해 주면 됩니다.

위 내용들을 조심스럽게 구현해 주면 $O(n)$ 시간에 결정 문제를 해결할 수 있고, 전체 문제가 $O(n \log n + n \log p)$ 에 해결됩니다. 이분 탐색을 사용하여 결정 문제를 $O(n \log n)$ 에 해결해도, 시간 초과를 받지는 않는 것 같습니다.

KAIST 2018 봄대회. QueryreuQ

어떠한 문자열에 존재하는 팰린드롬 부분문자열의 개수를 세기 위해서는 DP를 사용할 수 있습니다. $DP[i, j]$ 를 $S[i], S[i + 1], \ldots, S[j]$ 가 팰린드롬일 때 1, 아니면 0인 배열이라고 하면, $DP[i, i]$ 나 $DP[i, i - 1]$ 은 참이고, $DP[i, j]$ 는 $S[i] = S[j]$ 이며 $DP[i + 1, j - 1]$ 이 참일 때 참이 됩니다.

이 테이블을 각 쿼리마다 새로 만든다고 생각하지 말고, 매 쿼리마다 변홧값만 만든다고 생각해 봅시다. 길이 $l$ 인 문자열에 문자가 추가될 경우, $DP[*, l ]$ 만 새로 구해주면 되고 이는 $O(Q)$ 시간에 가능합니다. 문자가 제거될 경우, 그냥 해당 테이블을 무시해주면 되니까 $O(1)$ 시간에 가능합니다. 이 정도 최적화만으로 $O(Q^2)$ 시간에 문제가 해결됩니다.

그 외 Manacher Algorithm 등을 사용할 수도 있습니다. 이 문제는 Eertree를 잘 쓰면 $O(Q)$ 정도에도 풀 수 있는 풀이가 있습니다.

BOJ 1905. 상자 쌓기

이 문제는 여러 복잡도와 풀이로 해결할 수 있는데, 대개 $O(Q^2)$ 이하는 통과하고 $O(Q N \log N)$ 이상은 통과하지 않을 것입니다. $O(NM + Q \log N \log M)$ 풀이로도 통과할 수 있는데, 일단 여기서는 상대적으로 간단한 $O(Q^2)$ 풀이만 설명합니다.

각각의 $Q$ 개의 쿼리를, 2차원 격자판에 블록을 쌓는다 라고 생각할 수 있습니다. 초기 2차원 격자판이 비어있을 때, 직사각형 영역에 최댓값 $+X$ 의 값을 배정하는 것은, 높이 $X$ 의 직사각형 모양의 블록을 최대한 떨어뜨린 후 해당 영역에 놓는 것과 같다고 볼 수 있습니다.

이렇게 관점을 바꾸면, 이제 직사각형 영역의 높이가 아닌 각 "쿼리의 높이" 를 관리하는 방향으로 접근할 수 있습니다. 이는 동적 계획법으로 해결할 수 있습니다. $Area(i)$ 를 $i$ 번 쿼리의 영역이라 하고, $dp[i]$ 를, $i$ 번 쿼리 블록이 떨어질 때 닿은 윗면 높이라고 하면, $dp[i] = \max_{j < i, Area(j) \cap Area(i) \neq \emptyset} (dp[j]) + v[i]$ 라는 점화식이 성립합니다. 직사각형 영역의 최댓값은 결국 전체 쿼리의 최댓값과 동일하니, $\max_i dp[i]$ 를 출력하면 됩니다.

ROI 2016. Обитаемые горы

어떠한 선분이 방어탑에 의해 방어되지 않는다는 경우는 크게 두 가지가 있습니다.

• 이 선분을 무한히 늘린 직선이 방어탑 위를 지나가서 볼 수가 없는 경우
• 이 선분과 방어탑을 잇는 직선이 다른 선분에 의해 가로막혀서 볼 수가 없는 경우

첫 번째 경우는 굉장히 쉽게 판별할 수 있습니다. 문제 조건상 선분을 무한히 늘린 직선이 $ax + b$ 꼴로 쉽게 표현되기 때문입니다. $a x_i + b > y_i$ 인지 판별하면 됩니다. 두 번째 경우, 이 직선을 가로막는 다른 선분이 첫 번째 경우를 항상 만족함을 관찰할 수 있습니다. 이 다른 선분은 현재 보는 선분보다 방어탑에 더 가까이 있으며, 우리가 찾는 것은 방어탑에서 보이지 않는 가장 가까운 점이니, 이 경우는 해가 될 수 없고 고려하지 않아도 됩니다.

결국 문제는 $ax + b$ 꼴의 직선이 순서대로 $n$ 개 배치되어 있을 때, 현재 방어탑의 왼쪽/오른쪽 방향에서 $ax + b > y$ 를 만족하는 가장 가까운 직선을 찾는 것으로 변형됩니다. 가장 단순하게는 $O(nm)$ 에 해결할 수 있지만, 이는 시간 초과가 납니다.

이 문제는 특정 점을 끝점으로 하며 $max(ax + b) \le y$ 를 만족하는 가장 긴 구간을 찾는 문제라고 생각할 수 있습니다. 통상 이러한 문제에서 자주 사용하는 컨벡스 헐 트릭 (Convex Hull Trick, CHT) 을 생각해 봅시다. 만약에 어떠한 구간에 대한 $max(ax + b)$ 값을 빠르게 계산할 수 있다면, 구간의 길이를 이분 탐색해서 문제를 해결할 수 있습니다. 구간에 대한 $max(ax + b)$ 를 빠르게 계산하는 것은, 세그먼트 트리의 각 노드에, 해당 노드가 대표하는 구간의 직선으로 만든 CHT 자료구조를 구성하면 됩니다. 이러한 세그먼트 트리를 구성하면 구간에 대한 $max(ax + b)$ 를 계산하는 것이, $O(\log n)$ 개의 CHT 자료 구조에 대해 $max(ax + b)$ 를 계산하는 것과 동일해지기 때문입니다. 이 풀이를 그대로 구현하면:

• 세그먼트 트리 구성에 $O(n \log n)$ (단순히 하면 정렬로 인해 $O(n \log^2 n)$ 이지만 머지 소트와 같은 원리로 정렬과 동시에 트리를 구성할 수 있습니다.)
• 각 쿼리마다 $O(\log n)$ 번의 이분 탐색, 매 이분 탐색마다 $O(\log n)$ 개의 노드에 대해 CHT 쿼리, 각 쿼리는 이분 탐색이 필요하니 $O(\log n)$

으로 $O(n \log n+ m \log^3 n)$ 의 시간 복잡도가 되어 시간 초과가 납니다. 문제의 시간 제한이 널널하지 않기 때문에 로그를 두개 때야 하는데, 다음과 같이 하면 됩니다:

• 각 쿼리마다 이분 탐색을 하는 대신, 세그먼트 트리에서 현재 방어탑이 있는 위치에서부터 bottom-up으로 올라오면서, 부모의 다른 쪽 자식 (sibling, 예를 들어, 현재 노드가 $p$ 면 $p \oplus 1$ 번 노드) 가 $max(ax + b) > y$ 를 만족하면 해당 노드를 타고 내려가는 식으로 양 방향에서 가장 가까운 직선을 찾습니다. 이렇게 되면 한번의 탐색에 $O(\log n)$ 개의 노드를 보며, 이분 탐색이 없으니, $O(m \log^2 n)$ 이 됩니다.
• CHT에서 쿼리되는 $x$ 좌표가 증가하면 이분 탐색 없이 Two pointers로 문제를 해결할 수 있습니다. 초기 쿼리를 모두 $x$ 좌표 순으로 정렬하면 이 조건을 만족시켜줄 수 있으니, 각 쿼리당 $O(m \log n)$ 의 시간이 들고, Two pointers가 이동한 횟수는 CHT 크기 합에 amortize되니 총 $O((n + m) \log n)$ 에 쿼리가 해결됩니다.

두 최적화를 적용하면 시간 복잡도 $O((n + m) \log n)$ 에 문제가 해결됩니다.

BOJ 26460. 수열과 쿼리 41

Segment Tree Beats 를 사용하면 구간 최대화 쿼리를 하면서 여러 값들을 관리할 수 있음이 잘 알려져 있습니다. Segment Tree Beats를 활용하여 문제를 해결할 때, 일반적으로 노드에 들고 다니는 값은

• 최솟값
• 두번째 최솟값
• 최솟값만 바뀔 때 $O(1)$ 에 갱신할 수 있는 적절한 정보들

또 한편으로 구간 최대 부분합을 세그먼트 트리로 관리할 때 통상 관리하는 값은 전체 합 (sum), Prefix/Suffix 최대 합 (pfx, sfx), Subsegment 최대 합 (opt)입니다. 구간의 최솟값이 바뀔 때 이 수량들을 모두 효율적으로 갱신할 수 있을까요? 불가능하지만, 비슷한 시도는 해 볼 수 있습니다. 각 구간의 최대 합을 $x \times (\text{최적 구간 최솟값의 등장 횟수}) + (\text{최적 구간 최솟값 아닌 구간의 합})$ 과 같이, 최솟값 $x$ 에 대한 일차 함수로 정의합시다. 이 일차 함수를 비교할 때는, 최솟값이 정확히 현재의 값 이라는 가정하에 계산합니다. 만약 최솟값이 현재의 값에서 적당히 아주 조금 바뀌게 될 경우 이 일차 함수를 통해서 올바른 값을 계산할 수 있겠지만, 만약 최솟값이 바뀌어서 최적 구간이 달라지게 된다면 함수를 수정해야 합니다.

이게 문제가 되니 또 다른 방법을 사용합시다. 예를 들어서 Subsegment 최대 합을 계산할 때 우리는 다음 세 값 중에서 최댓값을 취합니다:

• 왼쪽 자식의 최대 합 (L.opt)
• 오른쪽 자식의 최대 합 (R.opt)
• 왼쪽 자식 Suffix 최대 합 + 오른쪽 자식 Prefix 최대 합 (L.sfx + R.pfx)

구간의 최대 합을 최솟값에 대한 일차 함수로 관리할 경우, 위 세 값 모두 일차 함수의 꼴로 나옵니다. 우리의 현재 전략은 $x = min[l, r]$ 일 때 이 3개 중 최대값인 직선을 고르는 것입니다. 만약, 서브트리에 대해서 값이 바뀌지 않는다면, 이 직선이 바뀌는 시점은 3개 직선 중 어떤 직선이 현재 직선을 교차해서 뛰어넘는 시점일 것입니다. 각 노드 $v$ 에 대해 Prefix, Suffix, Subsegment 에 대한 최대 합을 주는 직선이 바뀌는 시점을 $melt[v]$ 라고 정의합시다. 최대화 쿼리를 할 때, 두 번째 최솟값이 바뀔 때 뿐만 아니라, 서브트리의 $melt[v]$ 가 현재 바꾸는 최솟값 이하인 것이 존재한다면, 해당 서브트리로 타고 내려가면서 모두 다시 계산해 줍니다. 이렇게 될 경우, 모든 업데이트가 끝난 이후 전체 트리의 일차 함수가 올바름이 보장되기 때문에 모든 쿼리를 해결할 수 있습니다. 여담으로 이는 이 글의 Kinetic Segment Tree와 거의 동일한 원리입니다.

이제 중요한 것은 이 알고리즘의 시간 복잡도입니다. Segment Tree Beats의 원리를 생각해 보면 최솟값 갱신만 있을 때 $O((n + q) \log n)$ 에 문제가 해결되는 것은 명백합니다. 하지만 $melt[v]$ 를 풀어주기 위해서 얼마나 많은 시간이 들지 예측이 되지 않습니다. 이 부분을 증명하는 게 정답 코드를 짜는 것 이상으로 어렵다고 생각합니다. 다음과 같이 증명할 수 있습니다. (증명은 이 글 에서 가져왔습니다.)

먼저, pfx = max(L.pfx, L.sum + R.pfx) 와 같이 pfx, sfx 를 결정하는 조건은, 한번 L.sum + R.pfx 가 커지게 되면 다시는 L.pfx 가 이를 역전할 수 없습니다. 모든 값 업데이트가 배열의 원소를 증가시키기 때문에, 좌변의 증가는 무조건 우변의 증가로 이어지게 되어 있습니다. 고로 여기서 유도되는 Melt의 횟수는 쿼리가 몇개던간에 $O(n)$ 번으로 한정됩니다.

opt 쪽의 시간을 예측하기 위해 퍼텐셜을 사용합니다. 각 노드 $v$ 에 대해서 opt = max(L.opt, R.opt, L.sfx + R.pfx) 라는 조건문을 생각해 봅시다. $f(x) = max(a(x), b(x), c(x))$ 의 꼴인데, ($a, b, c$ 중 $f$ 보다 기울기가 큰 함수의 개수) * ($v$ 의 세그트리상 깊이) 를 $v$ 의 퍼텐셜로 정의합니다. 즉, 깊이 $d$ 의 노드가 가질 수 있는 퍼텐셜은 ${0, d, 2d}$ 입니다. 세그트리의 모든 연산을 살펴보면서 이 퍼텐셜 값의 시작과 갱신을 관찰합시다.

• 초기 퍼텐셜의 합은 $O(n \log n)$ 입니다.
• melt를 모두 풀어주었다는 가정 하에 구간 갱신은 $O(\log^2 n)$ 만큼의 퍼텐셜을 추가합니다.
• pfx, sfx 의 역전이 그 부모 의 opt 퍼텐셜을 바꿀 수 있습니다. 각 역전이 $O(\log n)$ 의 퍼텐셜을 증가하니 여기서도 $O(n \log n)$ 의 퍼텐셜이 추가됩니다.
  • 부모의 부모 의 opt 퍼텐셜이 바뀌는 건 여기서 고려할 필요가 없습니다. 역전을 반영하기 위해서 조상 전체를 푸는 것이 아닙니다. 부모만 풀어주고, 부모에 역전이 있으면 그건 또 거기서 풀어주고... 를 반복하는 겁니다.
• opt 의 역전이 일어날 경우 나의 퍼텐셜은 정확히 $d$ 만큼 감소합니다. 역전된 선분의 기울기가 $f$랑 동일해진 순간이기 때문입니다. 한편, 부모의 퍼텐셜은 $d-1$ 이하로 증가합니다. 하나의 직선 (L.opt 내지는 R.opt) 이 역전하는 가능성이 생겼기 때문입니다.

고로 총 $O(n \log n + q \log ^2 n)$ 의 퍼텐셜이 있고, 역전을 한 번 해소하면 이것이 $1$ 씩 감소합니다. 역전을 한번 해소할 때 $O(\log n)$ 시간이 들었으니, $O(n \log^2 n + q \log^3 n)$ 시간 복잡도에 문제가 해결됩니다. 증명을 봐도, 실제 코드 수행 시간을 봐도, 이 알고리즘의 실제 시간 복잡도가 $\Theta(\log^3 n)$ 이 나오게 되는 입력은 없을 것이라고 추정이 됩니다. 더 좋은 upper bound를 찾는 것은 여러분의 몫으로 남기겠습니다.

관련 있을 수도 있는 글들

• 2022.07.17 problem solving
• 2021.12.02 problem solving
• 2021.07.27 problem solving
• Klein's Algorithm for Computing Edit Distance on Tree
• CCO 2019 Shopping Plans
• 2021.01.17 problem solving
• 2020.08.14 problem solving
• 2020.08.09 problem solving
• 2019.12.26 problem solving

참고하면 좋은 글

• Semi-Local String Comparison