April 13, 2020 16:45

서론

수준급의 알고리즘 문제를 풀다 보면 다양한 장벽에 가로막히곤 합니다. 어려운 문제들 중에는 특히 쿼리형¹의 문제가 많은데, 이런 문제들은 단순한 방법으로 답을 도출해내는 것은 쉽지만 시간 복잡도를 줄이는 데에 복잡한 자료구조가 요구되어 난이도가 매우 높아지는 경우가 많습니다.

이러한 문제들의 의도는 주로 특수한 형태의 트리²나 이분 탐색 등을 활용하여 $O(Q\log^K{N})$ 꼴의 시간 복잡도를 만들어내도록 하는 것이지만, 일부 문제의 경우 $O((N+Q)\sqrt{N})$과 같이 루트가 시간 복잡도에 포함되는 것이 정해인 경우도 있습니다. 대표적인 것이 이전에 소개한 바 있는 Mo’s algorithm을 정해로 하는 문제들입니다. $O(N\sqrt{N})$은 비록 $O(N\log{N})$에 비하면 터무니 없이 큰 복잡도이지만, $O(N^2)$에 비하면 훨씬 작기 때문에 $N \approx 10^5$인 문제에서 약 1초 내에 실행되게 하는 데에 대체로 충분합니다.

이 글에서는 이렇게 루트가 시간 복잡도에 들어가는 것이 정해가 아닌 문제를 루트를 사용하여 제한에 절묘하게 들어맞도록 문제를 *뚫는* 방법에 대해 소개하고, 이를 적용하여 풀 수 있는 문제를 몇 개 풀이하도록 하겠습니다.

루트로 커버할 수 있는 시간 제한

루트를 시간 복잡도로 가지는 구현체는 (항상 그런 것은 아니지만) 대체로 상수가 크다는 문제점이 있습니다. $N \approx Q$를 가정할 때, Mo’s algorithm은 양끝 포인터가 움직이는 횟수가 최악의 경우 약 $\cfrac{3}{2}N\sqrt{N}$³번이나 되며, 구간을 $O(\sqrt{N})$개로 쪼개어 구간 합 구하기 문제를 푸는 풀이의 경우 최악의 경우 쿼리마다 거의 $3N$ 개에 달하는 업데이트를 요구합니다. 이외에도 많은 평방 분할 기법들은 단위 연산의 횟수에 있어 1보다 큰 상수를 가지는 경우가 많습니다. 이는 많은 나이브한 $O(N^2)$ 구현들이 $\cfrac{1}{4}$ 등의 작은 상수를 가지는 것과는 대조됩니다.

그렇지만 포기하기에는 이릅니다. 이러한 문제들에서 요구하는 정해에서 사용하는 자료구조들 역시 상수가 큰 경우가 많기 때문입니다. $N = 10^5$ 정도에서 $\sqrt{N}$은 $\log^2{N}$과 비슷한 값이 되기 때문에, $O(N \cdot log^2{N})$이 정해인 문제는 웬만해서는 루트로도 충분히 시간 내에 해결이 될 것으로 예측할 수 있습니다.

반면에 루트로 뚫리는 것을 정말로 원치 않는 문제들이 있습니다. 이들은 $N$에 $10^6$과 같은 큰 제한을 걸어 루트를 사용할 시 10억을 기본으로 가지고 가게 만들고는 합니다. 이런 경우에도 시간 제한을 통과할 수 있도록 최적화가 가능할 것인지는 뚫고자 하는 방법에 따라, 또한 정확히 몇 초가 주어지느냐에 따라 신중히 결정해야 할 것입니다.

루트로 쪼갤 수 있는 것

이 글에서 다루는 루트로 쪼개는 방법에는 크게 두 가지가 있습니다. 하나는 구간을 쪼개는 것이고, 다른 하나는 쿼리를 쪼개는 것입니다. 다음과 같이 정리할 수 있습니다.

구간 쪼개기

수열 문제 등에서 길이가 $N$인 구간을 $O(\sqrt{N})$개의 구간으로 쪼개는 것입니다. Mo’s algorithm은 여기에서 다루는 것과는 조금 다릅니다.

일반적으로는 쿼리와 완전히 겹치는 구간들을 묶어서 빠르게 관리할 수 있어야 하고, 개별적인 원소에 대한 업데이트가 구간에 빠르게 반영될 수 있어야 합니다. 쿼리가 하나 수행될 때마다 최대 $O(\sqrt{N})$개의 개별 원소와 $O(\sqrt{N})$개의 구간 업데이트가 이루어지도록 하는 것이 주 목적입니다.

구간 쿼리를 처리하기 위해 세 종류의 구간을 찾아 개별적으로 처리를 하게 되는데, 쿼리의 왼쪽 끝 지점이 속한 구간과, 오른쪽 끝 지점이 속한 구간, 그리고 그 사이에 있는 구간들입니다. 왼쪽 끝 / 오른쪽 끝 지점에 대해서는 보통 원소과 구간 전체의 답을 완전히 업데이트 해주는데, 구간의 크기가 $O(\sqrt{N})$이므로 이렇게 해도 느리지 않기 때문입니다. 두 구간 사이에 있는 구간들은 보다 빠르게, 보통은 $O(1)$에 구간 전체에 대한 답만 빠르게 업데이트하고 지나가야 합니다. 그러한 구간이 총 $O(\sqrt{N})$개 존재하기 때문입니다. 필요에 따라서는 lazy하게 쿼리를 미뤄두고 지나갈 수도 있습니다.

쿼리 쪼개기

$Q$개의 쿼리를 $O(\sqrt{Q})$개 또는 $O(\sqrt{N})$개 단위로 쪼개는 것입니다. 이 방법은 주로 $O(\sqrt{N})$개의 쿼리마다 ‘초기화’를 하는 기법을 동반하는데, 매 쿼리를 주어진 수열 등에 반영하는 것은 효율적으로 할 수 없으나 $O(\sqrt{N})$개의 쿼리를 몰아서 반영하는 것은 $O(N)$ 정도의 시간이 걸릴 때 사용하게 됩니다. 초기화는 지금까지의 모든 쿼리 내용을 수열에 직접 반영시키고, 다음 초기화 시점까지를 위한 전처리를 수행해주는 것을 의미합니다.

이 방법의 장점은 주로 쿼리에 의해 구간이 나누어져야 하는 경우에 나타납니다. 구간이 나누어질수록 이후 매 쿼리마다 확인해야 하는 구간이 점점 늘어나는데, 그러다 보면 쿼리를 $Q$번 수행했을 때 $Q^2$개의 구간을 보게 될 수도 있습니다. 이를 $O(\sqrt{N})$개가 진행될 때마다 전체 초기화를 해서 다시 구간의 개수를 줄임으로써 시간 복잡도를 안정시킬 수 있습니다. 또는 구간이 아니더라도 초기화 시점으로부터 현재까지의 쿼리까지 ‘필요한 부분만’ 뽑아 진행시키고 다시 원래대로 되돌리는 방법도 활용 가능합니다.

구간 쿼리 문제에서 쿼리 쪼개기를 하는 방법에는 두 가지가 있습니다.

1. $O(\sqrt{N})$개씩의 쿼리를 미리 보고, 그 쿼리들에 나타나는 시작점 / 끝점만을 모아 그 점들을 기준으로 구간을 분할하는 오프라인 풀이를 구상할 수 있습니다. 아래 1번 문제에서 구체적인 예시가 있습니다.
2. 또는 일단 구간을 $O(\sqrt{N})$개 단위로 쪼개놓고, 추가로 $O(\cfrac{Q}{\sqrt{N}})$개 쿼리에 의해 나타나는 구간을 더 쪼개는 방법도 있습니다. 이는 온라인 풀이를 가능하게 하기도 하면서, 쪼개진 구간에 대한 재계산이 구간의 길이에 비례하게 걸릴 때 최악의 경우에도 $O(\sqrt{N})$ 시간이 걸리게 만들어 줍니다.

예시 문제 풀이

지금까지 소개한 기법들을 응용하여 풀 수 있는 문제를 몇 개 소개하려고 합니다. 전반적으로 난이도가 높은 문제들이기 때문에 전체 코드는 너무 길 뿐더러 시간을 보다 단축하기 위한 여러 최적화 기법들이 많이 들어가 있어 가독성이 떨어지므로 직접 첨부하지 않고 링크를 대신 남기겠습니다.

문제 1. 나는 행복합니다

• 시간 복잡도: $O(Q\sqrt{\vert S\vert })$
• 정답 코드: http://boj.kr/79ef8a1fb16344f7b94cc718b92b0fc9 ⁴

이 문제는 정해에 비해 루트 풀이의 구현이 훨씬 간단하고, 실제로도 루트로 해결한 분이 일부 있는 것으로 알고 있습니다. 편의상 $\vert S\vert $를 $N$으로 표기하겠습니다. 숫자의 개수가 0에서 9까지 10개인 점을 감안하면 제법 큰 상수가 붙지만, 가벼운 연산들로 이루어져 있고 시간 제한도 3초이기 때문에 적당한 최적화 기법을 사용한다면 충분히 통과할 수 있는 제한입니다. 이 풀이에는 두 가지 핵심적인 아이디어가 요구됩니다.

아이디어

첫 번째 아이디어는 $\sqrt{N}$개의 쿼리마다 초기화를 수행하는 것입니다. 이렇게 초기화가 되는 시점 사이의 쿼리들을 모아서 처리하는 것은 쿼리 쪼개기에서 자주 활용됩니다. 쿼리들끼리 미치는 영향이 과도해지지 않도록 적당한 선인 $\sqrt{N}$개에서 끊어줍니다. 이 문제의 경우 이 초기화를 $O(N)$에 할 수 있고 초기화를 $O(\cfrac{Q}{\sqrt{N}})$번 수행하기 때문에 총 $O(Q\sqrt{N})$의 초기화 시간이 소요되는데, 자세한 과정은 후술하겠습니다. 이렇게 초기화 시점을 기준으로 그 사이의 쿼리들을 묶어준 것을 ‘블록’이라고 부르겠습니다.

두 번째 아이디어는 한 ‘블록’ 내의 쿼리들(1번, 2번 포함)이 나타내는 구간의 시작점과 끝점들을 기준으로 그 사이의 원소들을 모아서 처리할 수 있는 자료구조를 만드는 것입니다. 임의의 구간을 처리할 수 있도록 하는 자료구조는 까다롭기 때문에, 실제로 처리해야 할 구간들을 최소 단위로 미리 나누어놓고 각 구간이 다른 구간에 의해 간섭받지 않게 해줍니다. 각 쿼리에 대해 두 지점만이 존재하기 때문에, 각 ‘블록’은 최대 $O(\sqrt{N})$개의 구간으로 쪼개지게 됩니다.

구조

따라서 기본 구조는 모든 쿼리를 순차적으로 진행하되, 루트 개의 쿼리가 진행될 때마다 현재까지 수행된 쿼리들의 결과를 배열에 모두 반영하고, 다시 이후 루트 개의 쿼리에서 등장하는 지점들로 구간을 나누는 방식이 됩니다.

풀이

나누어진 구간들 각각에 대해서는 $P[0..9]$ 배열을 두어 $P[i]$는 이 ‘블록’이 시작하는 시점에서의 $i$가 현재 이 구간에서 가지는 값을 기록하게 합니다. 또한 $X[0..9]$ 배열의 $X[i]$는 이 ‘블록’이 시작하는 시점에서의 전체 문자열을 10진수로 표현했을 때 $i$들이 나타나는 자릿수들의 합을 $\mod 998244353$한 값을 저장해 둡니다.⁵ 그러면 매 1번 쿼리마다 최대 $O(\sqrt{N})$개의 구간에 대해 $P[i] = from$인 $i$를 모두 찾아 $P[i] = to$로 바꾸어주면 되므로 총 $O(Q\sqrt{N})$의 시간이 소요되고, 매 2번 쿼리마다 $O(\sqrt{N})$개 구간에 대해 $P[i] \times X[i]$를 곱한 것을 더해준 뒤, 뒤에 남은 자릿수만큼을 mod inverse 연산을 통해 곱해주어 답을 구할 수 있으므로 역시 $O(Q\sqrt{N})$ 시간이 소요됩니다. 루트 개의 쿼리마다 전체 배열을 재계산하고 이후 루트 개의 쿼리의 시작 / 끝 지점으로 구간을 나누는 데에 $O(N)$⁶ 시간이 소요되므로, 총 시간 복잡도 역시 $O(Q\sqrt{N})$이 됨을 볼 수 있습니다.

문제가 요구하는 기본 난이도가 낮지는 않지만, 루트로 쪼깬 후의 구현은 비교적 나이브하다고 볼 수 있습니다. 특별히 어려운 자료구조를 사용하지 않고도 루트 개마다의 초기화 연산을 통해 개별 쿼리들은 편하게 처리할 수 있도록 만들었기 때문입니다.

문제 2. 수열과 쿼리 31

• 시간 복잡도: $O((N+M)\sqrt{N})$
• 정답 코드: http://boj.kr/24f48bafcd9c4616abe4912d50993b5a

이 문제는 구간을 쪼개는 아이디어는 비교적 간단한 편이지만, 세부적인 구현이 꽤 복잡해집니다.

기본적으로는 1번 문제와 비슷하게 $O(\sqrt{N})$개 쿼리마다 초기화를 수행하고, 이후 $O(\sqrt{N})$개 쿼리에 등장하는 지점들로 수열을 나누어서 풀 수 있습니다. 하지만 쿼리에 등장하는 지점들을 기준으로 구간을 나누는 방법은 초기화 시점마다 이후 루트 개의 쿼리를 미리 확인해야 하는 ‘오프라인 풀이’를 요구하므로, 각 쿼리에 대한 답을 곧바로 구한 뒤 다음 쿼리로 넘어갈 수 있도록 하는 ‘온라인 풀이’가 가능하도록 변형을 시켜보겠습니다. 물론 이 문제에서는 온라인 풀이가 필요하지 않지만, 루트로 쪼개는 테크닉이 온라인으로도 가능하다는 것을 보이기 위함입니다.

구조

구간을 쿼리에 나타난 위치 대신에 $\sqrt{N}$개 단위로 미리 쪼개놓아 보겠습니다. 그러면 각 ‘블록’이 초기화될 때마다 $\sqrt{N}$개의 구간이 생성될 것이므로, 한 번의 초기화가 $O(N)$ 시간을 소요하고 각 쿼리가 $O(\sqrt{N})$ 시간이 소요되게 만들면 목표 시간 복잡도를 달성할 수 있습니다.

각 구간은 서로 연결 리스트로 연결시켜놓고, 시작 부분에 연속적으로 위치한 1의 개수, 끝 부분에 연속적으로 위치한 1의 개수, 구간 내에서 가장 길게 연속적으로 있는 1의 개수를 저장해 두고, 마지막으로 해당 구간이 현재 뒤집힌 상태인가를 저장해 둡니다.

struct A {
	char *p, *a;
	bool rev;
	int sz;
	int pmax, smax, max;
	int prev, next;
};

이 코드에서 a는 해당 구간이 처음 생성될 때의 해당 구간의 수열이고, p는 현재 시점에서 해당 구간의 첫 번째 수의 위치를, sz는 구간의 크기입니다. pmax, smax, max는 각각 시작 부분, 끝 부분, 그리고 전체에서의 최대 연속한 1의 개수이며, prev, next는 각각 이전, 이후 구간의 인덱스를 나타냅니다.

풀이

1번 쿼리들에 대해서는 연결 리스트 전체를 순회하면서 두 개의 구간을 찾는데, 하나는 $L$이 속한 구간이고, 다른 하나는 $R$이 속한 구간입니다. 둘 사이에 있는 구간들에 대한 처리는 간단합니다. rev를 뒤집어주고 prev와 next를 swap해주기만 하면 됩니다.

문제는 $L$과 $R$이 속한 구간에 대한 처리인데, 이 과정을 구체적으로 구현하는 것은 상당히 복잡하므로 개념적인 것만 서술하겠습니다. $L$이 속한 구간을 예로 들면, 이 구간에서 정확히 $L$이 나타내는 위치를 찾아 그 위치를 기준으로 둘로 나누어 한쪽을 새로운 구간에 넣어줍니다. 나누어진 구간 각각에 대해서는 pmax, smax, max 값 등을 전부 재계산해주며, 링크드 리스트가 올바른 형태가 될 수 있도록 기존 / 새로운 구간의 prev, next 포인터를 재조정해줍니다. 비슷한 과정을 $R$이 속한 구간에 대해서도 해줄 수 있습니다.

각 1번 쿼리마다 새로 생성되는 구간이 최대 2개이며, 이렇게 구간의 개수가 계속 늘어나는 것은 ‘블록’의 크기인 $\sqrt{N}$뿐이기 때문에 리스트 전체를 순회하는 시간 역시 $O(\sqrt{N})$임을 확인할 수 있고, 초기화 후 각 구간의 크기가 $O(\sqrt{N})$이고 이후 구간의 크기가 늘어나는 일도 없으므로 $L$과 $R$이 속한 구간을 둘로 분할하는 것 역시 $O(\sqrt{N})$ 시간만이 소요됨을 볼 수 있습니다.

2번 쿼리는 비교적 간단합니다. 똑같이 리스트 전체를 순회하면서 $L$과 $R$이 속한 구간을 찾은 뒤, 그 사이를 지나가면서 pmax, smax, max 등을 적절히 이용하여 현재까지 찾은 최대 연속 1의 길이를 갱신해주면 됩니다. 여기서 확인하게 되는 구간의 수 역시 $O(\sqrt{N})$이므로, 쿼리의 종류에 관계 없이 시간 복잡도가 $O(\sqrt{N})$이 되며, 따라서 전체 시간 복잡도는 $O(M\sqrt{N})$이 됨을 확인할 수 있습니다.

문제 3. LCS 5

• 시간 복잡도: $O(\vert A\vert \vert B\vert )$
• 공간 복잡도: $O(\vert B\vert \sqrt{\vert A\vert })$
• 정답 코드: http://boj.kr/f951d67f224240b89a46bd906d7c1f61

이 문제는 작은 메모리 제한 때문에 일반적인 LCS 알고리즘으로 풀 수 없고 논문급의(?) 사전 지식이 요구되는 문제이지만, 매우 독특한 루트 쪼개기를 통해 말 그대로 뚫어내는 것이 가능합니다.

아이디어

기본적인 방향은 LCS를 $O(\vert A\vert \vert B\vert )$ 시간에 푸는 방법과 동일합니다. $DP[\vert A\vert + 1][\vert B\vert + 1]$ 배열을 만들고 $A[i - 1] == B[j - 1]$ 이면 $DP[i][j] = DP[i - 1][j - 1] + 1$, 아니면 $DP[i][j] = \max(DP[i - 1][j], DP[i][j - 1])$을 적용해서 나가는 기초적인 DP 풀이입니다. 하지만 이 문제는 이러한 DP 배열을 생성하는 것조차 불가능한 메모리 제한을 가지고 있습니다. 그래서 다음과 같은 아이디어를 생각할 수 있습니다.

$DP$를 $A$ 문자열에 대해 $\sqrt{\vert A\vert }$ 단위로 진행한 결과를 저장해두면, 크기가 $O(\vert B\vert )$인 중간 결과가 총 $O(\sqrt{A})$개 생성되고, $DP$ 배열 역시 매번 기존 공간을 재사용하면 되기 때문에 두 배열 모두 $O(\sqrt{\vert A\vert }\vert B\vert )$ 크기만을 요구하게 됩니다. 이러한 구조를 활용해서 문제를 해결할 수 있습니다.

풀이

단순히 LCS의 길이를 구하고자 하는 문제는 $O(\vert B\vert )$의 공간만을 사용해서 풀 수 있다는 점은 널리 알려져 있습니다. $A$의 짝수 번째와 홀수 번째 문자에 따라 번갈아 가며 배열 공간을 재사용하면 되기 때문입니다. 이러한 과정을 통해 먼저 LCS의 길이를 찾는 과정을 수행할 수 있고, $\sqrt{\vert A\vert }$의 배수인 $i$마다 $DP[i \% 2][0..\vert B\vert ]$를 중간 결과를 저장하는 배열 $X[\sqrt{\vert A\vert } + 1][\vert B\vert + 1]$에 차곡차곡 저장해나갈 수 있습니다.

LCS의 길이를 구한 후에는 역추적을 해야 하는데, 이를 위해서 $i$가 큰 것부터 $X[i]$에서 $X[i + 1]$까지의 과정을 $DP$ 배열을 통해 재계산한 후 해당 구간에 대한 정답 문자열을 일반적인 역추적 기법을 통해 따라가며 만들 수 있고, 이 과정이 끝나면 다시 $DP$의 공간을 활용하여 $X[i - 1]$에서 $X[i]$까지의 과정을 재현하는 것을 반복하여 전체 LCS를 복구할 수 있게 됩니다.

루트 개로 쪼개더라도 여전히 메모리 제한에 걸리기 쉽기 때문에 iostream도 사용하지 말아야 하고, short 등을 사용하여 극단적으로 압축하는 등의 노력이 필요하기 때문에 ‘비비는’ 연습에 아주 좋은 풀이라고 할 수 있습니다.

문제 4. 수열과 쿼리 35

• 시간 복잡도: $O(M\sqrt{N}\log{N})$
• 정답 코드: http://boj.kr/20c96b68d36c4dc6867e9766d26a040f

이 문제의 풀이는 위의 수열과 쿼리 31 풀이의 심화 버전이라고 할 수 있습니다. 전체적인 구조가 유사하므로, 달라지는 부분에 대해서만 서술하겠습니다.

구조

struct A {
	int *p, *a;
	bool ok;
	int sz;
	int max, min;
	int max2, min2;
	int prev, next;
	int *s, *t;
};

a, p, sz, prev, next는 수열과 쿼리 31에서의 그것과 동일한 역할입니다. max와 min은 이 구간에서 가장 큰 값과 가장 작은 값을 나타냅니다. min2는 해당 구간의 원소 중 더 왼쪽에 작은 값이 존재하는 원소 중 가장 작은 것을 의미하며, max2는 해당 구간의 원소 중 더 오른쪽에 큰 값이 존재하는 원소 중 가장 큰 것을 의미합니다. t는 해당 구간의 원소를 정렬해놓은 배열이며, s는 이 배열에서의 오프셋을 a와 동일하게 맞추어주기 위한 포인터입니다. ok는 현재 구간만으로 길이 3의 증가하는 부분 수열이 존재하는지 여부를 나타냅니다.

풀이

수열과 쿼리 31과 동일한 방식으로 진행합니다. 다만 이번에는 찾아야 하는 지점이 $l$, $r$뿐만 아니라 $r-k$에 해당하는 지점도 찾아야 한다는 차이점이 있습니다. 이 세 지점에 의해 잘라지는 구간들을 잘 나누어 주고 연결 리스트를 다시 잘 이어붙이는 과정이 굉장한 구현 난이도를 자랑하지만, 이 글의 핵심과는 거리가 멀기 때문에 자세히 보지는 않겠습니다. 이렇게 잘린 최대 6개의 구간들에 대해서는 재계산을 해주며, 재계산에 정렬이 포함되기 때문에 쿼리당 $O(\sqrt{N}\log{N})$ 시간이 소요됩니다.

쿼리가 수행한 후의 답을 계산하기 위해서는 전체 구간을 순회하면서 다음 중에 하나가 존재하는지를 찾으면 됩니다.

1. ok == true인 구간
2. 현재 구간보다 왼쪽에서 가장 작은 값과, 현재 구간보다 오른쪽에서 가장 큰 값 사이의 값이 존재하는 구간⁷
3. 현재 구간보다 왼쪽에서 가장 작은 값보다 현재 구간의 max2가 더 크거나, 현재 구간보다 오른쪽에서 가장 큰 값보다 현재 구간의 min2가 더 작은 구간

전체 구간에 대해 1번, 3번은 $O(\sqrt{N})$ 시간에 해결이 가능하며, 2번은 $O(\sqrt{N}\log{N})$ 시간에 해결할 수 있으므로 모든 쿼리를 수행하는 데에 $O(M\sqrt{N}\log{N})$ 시간이 소요되는 것을 볼 수 있습니다.

문제 5. 자료 구조

• 시간 복잡도: $O(N+Q\sqrt{N})$
• 공간 복잡도: $O(N)$
• 정답 코드: http://boj.kr/4e3a99b8e53443de8cc1de0feb57f50c

쿼리 중에 ‘삽입 쿼리’가 있어 난이도가 있어 보이는 문제입니다. 게다가 나머지 쿼리들까지 효율적으로 관리하면서 자료 구조를 유지시키기가 상당히 어려워 보입니다. 하지만 이 문제 역시 구간을 루트 개로 쪼개어 효율적으로 관리하는 것이 가능합니다.

기본 아이디어는 수열과 쿼리 31과 비슷하게 구간을 미리 $O(\sqrt{N})$개 단위로 쪼개놓고 시작하는 풀이입니다. 다만, 이 문제에서는 초기화가 필요하지는 않습니다. 이때 각 쿼리를 어떻게 효율적으로 처리할 수 있을지가 관건입니다.

구조

using ll = long long;
struct A {
	vector<ll> v;
	ll a, b, x;
	ll sum;
};

v는 해당 구간의 원소들을 순서대로 모아놓은 배열입니다. a와 b는 2번 쿼리를 위한 변수, x는 1번 쿼리를 위한 변수인데, 구체적인 사용 방법은 후술하겠습니다. sum은 현재 구간의 원소들의 합을 저장한 값입니다.

풀이

1번과 2번 쿼리의 범위 내에 완전히 포함되는 하나의 구간에 대해 합을 구하는 것은 $O(1)$ 시간에 할 수 있습니다. 구간의 길이가 $L$이라고 한다면,

• 1번 쿼리: $XL$로 합을 변경.
• 2번 쿼리: 해당 구간의 첫 번째 원소가 쿼리의 $K$번째 원소라면, 쿼리의 기존 합에 $\cfrac{(K+L)(K+L-1) - K(K-1)}{2}X$ 를 더함.

와 같은 과정을 통해 구간의 합을 갱신할 수 있습니다. 이러한 구간이 항상 $O(\sqrt{N})$개 존재한다고 가정하면 완전히 포함되는 구간에 대한 1번, 2번 쿼리에 의한 업데이트는 $O(\sqrt{N})$에 가능합니다.

문제는 3번 쿼리와 1, 2번 쿼리 중 그 범위에 완전히 포함되지 않는 구간들입니다.⁸ 1번 쿼리의 범위에 완전히 포함되지 않는 구간의 경우 포함되지 않은 원소들의 합을 알아야 업데이트 후의 최종 합을 구할 수 있기 때문입니다. 따라서 이러한 구간들의 경우 원소들의 값을 완전히 업데이트 해주는 방법을 사용합니다.

그런데 그렇게 되면 다시 앞의 1, 2번 쿼리의 범위에 완전히 포함된 구간들의 경우에도 단순히 합만 구하는 것으로는 부족하고, 실제 원소의 값을 기록해주어야 한다는 문제점이 생깁니다. 그래서 이런 경우들에 한 가지 기능을 추가해 주는데, 이것이 a, b, 그리고 x입니다.

1번 쿼리부터 살펴보면, 구간 전체를 x로 바꾸는 것은 기존의 값이 무엇이었든지에 관계 없이 이후 재계산 때 x로 덮어씌우기만 하면 됨을 볼 수 있습니다. 따라서 구간 전체에 1번 쿼리가 들어가는 경우 2번 쿼리와 연관된 a, b를 지우고 x에 해당 값을 넣어두기만 하면 됩니다.

반면에 2번 쿼리가 구간 전체에 들어가려면 기존의 원소 값이 중요해집니다. 만일 이 구간 전체에 대한 가장 최신 쿼리가 1번이었다면 나중에 재계산 때 그 값으로 먼저 덮어씌워줄 것을 기대할 수 있으므로 1번 쿼리는 신경쓰지 않아도 됩니다. 2번 쿼리끼리는 누적시키는 것이 가능합니다. 구간 전체에 2번 쿼리가 겹쳐지는 것은 등차수열들을 서로 더하는 것과 같으므로, a를 초항으로, b를 공차로 정의하여 누적시키면 됩니다.

3번 쿼리는 이러한 게으른 계산 없이 무조건 재계산을 시키면 됩니다. 해당 위치를 찾아 그 자리에 원소를 끼워넣고 재계산을 하면 됩니다. 하지만 여기에는 한 가지 문제점이 있는데, 원소를 끼워넣는 곳이 배열이기 때문에 임의의 위치에 원소를 삽입하는 것은 최악의 경우 해당 배열의 크기에 비례하는 시간이 걸리므로, $Q$번 원소를 끼워넣는 것은 최악의 경우 $O(Q^2)$의 시간 복잡도가 요구됩니다. 그래서 여기에 한 가지 조건을 끼워넣는데, 그 크기가 $O(\sqrt{N})$인 어떤 크기를 초과하면 배열을 양분하여 새로운 구간을 만드는 것입니다. 이렇게 하여 한 구간의 크기를 항상 $O(\sqrt{N})$ 이하로 유지할 수 있습니다. 이 과정은 수열과 쿼리 35에서 했던 것처럼 연결 리스트를 사용해도 되지만, 이 문제에서는 구간의 순서가 뒤바뀔 일은 없기 때문에 단순히 구간들이 담긴 배열을 뒤로 한 칸씩 밀어도 됩니다. 이렇게 구간이 분할되는 일이 최대 $O(\cfrac{Q}{\sqrt{N}})$번만 발생하는데, 모든 구간을 전부 뒤로 한 칸씩 밀더라도 옮겨지는 원소가 $O(N)$개 뿐이기 때문에 총 $O(Q\sqrt{N})$번의 연산만이 필요한 것을 볼 수 있습니다.

재계산을 할 때는 x에 저장된 1번 쿼리를 먼저 처리하고, 그 후에 a, b에 저장된 2번 쿼리를 처리해야 합니다. 그 후 평범하게 구간 내의 모든 원소의 합을 구해서 sum에 저장하기만 하면 됩니다.

마지막으로 4번 쿼리는 단순히 모든 구간을 순회하면서 시작점과 끝점이 포함된 구간은 재계산 후 직접 원소들의 합을 구하고, 그 사이에 있는 다른 구간들은 sum을 바로 더하면서 진행하면 되므로, 이 과정 역시 $O(Q\sqrt{N})$ 시간이 소요됩니다.

시간 복잡도 분석

• 재계산: 구간의 크기가 항상 $O(\sqrt{N})$ 이하임이 보장되므로 $O(\sqrt{N})$ 시간.
• 1번 쿼리: $O(\sqrt{N})$개의 구간을 보고, 이 중 최대 2개의 구간에 대해 재계산하므로 $O(\sqrt{N})$ 시간.
• 2번 쿼리: 1번 쿼리와 동일.
• 3번 쿼리: 원소 삽입에 $O(\sqrt{N})$ 시간. 구간 분할이 $O(\cfrac{Q}{\sqrt{N}})$번 일어나고 각각이 $O(N)$ 시간이 소요되므로 amortized $O(\sqrt{N})$.
• 4번 쿼리: $O(\sqrt{N})$개의 구간을 보고 이 중 2개는 재계산 및 $O(\sqrt{N})$개의 합 연산. 나머지 구간은 $O(1)$에 계산.
• 총합: $O(Q\sqrt{N})$.

마치며

루트 쪼개기는 멋진 자료구조를 사용하는 것보다는 시간 복잡도 분석과 구현에 초점이 있고, 정해보다는 대체로 많은 연산을 요구하는 것을 커버하기 위하여 최적화에 힘을 들여야 한다는 점에서 그다지 아름답지 않아 보일지도 모르겠습니다. 게다가 루트가 아무리 작다고 해도 수학적으로 임의의 $p>0$에 대해 $\log^p$보다 항상 크다는 점도 분명한 단점입니다.

하지만 문제를 푸는 입장에서, 어떻게 보면 ‘현실적인’ 제한 내에서의 풀이를 찾는다는 점에서는 이러한 방법이 정해에 밀리지 않는다고 볼 수도 있겠습니다. 루트 쪼개기는 문제를 푸는 방법은 한 가지가 아니라는 것을 보여주는 대표적인 예시가 아닐까 생각합니다.