170. Mo's Algorithm

이번에는 제곱근 분할법을 수열에 적용하는 방법을 알아보자.

 

모스 알고리즘(Mo's Algorithm)^[각주:1]은 제곱근 분할법을 이용하여 세그먼트 트리 등의 자료 구조로 처리하기 어려운 쿼리를 처리하는 방법이다. 제곱근 분할법을 수 자체에 적용할 때는 제곱근 이하와 이상, 두 부분을 따로 다루었는데 제곱근 분할법을 길이가 $n$인 수열에 적용하면 $\sqrt{n}$ 정도의 길이를 갖는 $\sqrt{n}$개의 구간을 기준으로 접근하게 된다는 차이점이 있다는 것은 제곱근 분할법을 수에 적용하는 방법을 소개할 때도 언급했다.

 

그러면 모스 알고리즘의 작동 방법을 알아보자. 여기서 $\sqrt{n}$은 전부 근삿값이며 적당히 가까운 정수를 사용하면 된다. 또한 처리하는 쿼리들은 구간 $[l, r]$로 나타낼 수 있으며 한 쿼리가 다른 쿼리에 영향을 주지 않는다.

    1. 길이가 $n$인 수열을 길이가 $\sqrt{n}$인 $\sqrt{n}$개의 연속된 구간으로 분할하고 앞에서부터 차례로 $1, 2, \ldots $\sqrt{n}$으로 번호를 매긴다. (분할된 구간들을 주로 버킷(Bucket)이라고 부른다.)

    2. 쿼리를 $l$이 속한 버킷의 번호 순서대로, 번호가 같다면 $r$이 증가하는 순서대로 정렬한다. (이것은 나중에 다룰 오프라인 쿼리 테크닉을 적용한 것이다.)

    3. 정렬된 쿼리를 앞에서부터 하나씩 처리하는데, 이전 쿼리의 결과를 활용할 수 있다.

 

3번 과정은 상당히 막연하게 적혀 있다. 구체적으로 어떻게 하는 건지 구간 합을 구하는 문제를 예시로 들어 확인해 보자.

길이가 $20$인 수열 $a: \{a_1, a_2, \ldots, a_{20}\}$ 있고, 구간 $[l, r]$에 포함된 수들 $a_l, a_{l + 1}, \ldots, a_{r - 1}, a_r$의 합을 구하는 쿼리를 처리해야 한다. 주어진 쿼리들이 다음과 같다면,

$$Q_1: [4, 7], Q_2: [14, 18], Q_3: [5, 15], Q_4: [3, 20], Q_5: [6, 6],$$

$$Q_6: [10, 15], Q_7: [7, 11], Q_8: [4, 16], Q_9: [10, 12], Q_{10}: [1, 11]$$

$4 < \sqrt{20} < 5$이므로 크기가 $4$인 버킷 $5$개나 크기가 $5$인 버킷 $4$개로 분할하는 것이 일반적일 것이다. 여기서는 크기가 $4$인 버킷 $5$개로 분할하기로 한다. 그리고 나서 쿼리를 정렬하면 다음과 같다.

$$Q_1: [4, 7], Q_{10}: [1, 11], Q_8: [4, 16], Q_4: [3, 20], Q_5: [6, 6],$$

$$Q_7: [7, 11], Q_3: [5, 15], Q_9: [10, 12], Q_6: [10, 15], Q_2: [14, 18]$$

• 이제 이 순서대로 합을 구하면 된다. 합을 구하는 과정은 정말 단순하다. 그냥 이렇게 하면 된다. 이전 쿼리에서 주어진 구간이 $[l_1, r_1]$이고 이 쿼리의 답이 $s$이며 그 다음 쿼리에서 주어진 구간이 $[l_2, r_2]$라고 하면,
• $l_1 > l_2$인 경우 $s$에 $\sum_{i = l_2}^{l_1 - 1}a_i$를 더한다.
• $l_1 < l_2$인 경우 $s$에서 $\sum_{i = l_1}^{l_2 - 1}a_i$를 뺀다.
• $r_1 > r_2$인 경우 $s$에서 $\sum_{i = r_2 + 1}^{r_1}a_i$를 뺀다.
• $r_1 < r_2$인 경우 $s$에 $\sum_{i = r_1 + 1}^{r_2}a_i$를 더한다.

즉 두 구간의 차이에 해당하는 원소들을 더하고 빼 주기만 하면 된다는 것이다. 이때 누적합 같은 것을 안 쓰고 하나씩 일일히 더하고 빼도 된다는 점이 중요하다. 이렇게 할 때 연산 횟수가 어느 정도 되는지 살펴보자. 쿼리의 수는 $q$이다.

• 인접한 쿼리에서 왼쪽 구간의 차이 $|l_1 - l_2|$가 $\sqrt{n}$ 이상이려면 $l_1$과 $l_2$가 서로 다른 버킷에 속해 있어야 한다. 쿼리를 구간의 왼쪽 끝이 속한 버킷 순서대로 정렬했으므로 이런 경우는 최대 $\sqrt{n}$번 나온다. 또한 이런 경우에 발생하는 구간의 차이를 모두 합쳤을 때 세 개 이상이 겹치는 경우가 존재하지 않으므로 $|l_1 - l_2|$ 중 $\sqrt{n}$ 이상인 것들의 합은 최대 $2n$이다.
• 나머지 $q - \sqrt{n}$개의 인접한 쿼리들은 전부 $|l_1 - l_2|$가 $\sqrt{n}$ 미만이다. 따라서 $|l_1 - l_2|$ 중 $\sqrt{n}$ 미만인 것들의 합은 최대 $q \sqrt{n} - n$이다.
• 오른쪽 구간은 왼쪽 끝이 같은 버킷에 속한 경우 오름차순으로 정렬되므로 $r_1 > r_2$인 상황은 왼쪽 끝이 서로 다른 버킷에 속할 경우에만 발생한다. 따라서 $r_1 > r_2$인 경우는 최대 $\sqrt{n}$번 나오고, 이 경우 $|r_1 - r_2|$의 합은 최대 $n \sqrt{n}$이다.
• $r_1 > r_2$인 경우를 제외하면 쿼리들을 $\sqrt{n}$개의 그룹으로 분리할 수 있다. 각 그룹에서 $|r_1 - r_2|$의 합은 $n$ 이하이므로 이 경우 $|r_1 - r_2|$의 합은 최대 $n \sqrt{n}$이다.
• 이상을 다 더하면 $(2n + q) \sqrt{n} + n$이고, 시간복잡도로 나타내면 $O((n + q) \sqrt{n})$이다.

$n$이 $q$에 비해 매우 큰 경우가 아니라면 대충 쿼리 하나당 $O(\sqrt{n})$ 시간에 처리할 수 있다는 결과가 나온다. 물론 평균적으로 그렇다는 거고 실제로는 훨씬 빠르게 처리되는 쿼리와 더 느리게 처리되는 쿼리 등이 섞여 있다.

 

구현은 다음과 같다. 위에서 설명한 내용과 세부적으로 약간 다르지만 기본적인 틀은 동일하다.

#import<bits/stdc++.h>
using namespace std;
struct Query{int i, b, l, r, s;};
int a[100005];
vector<Query> query;
int C1(Query a, Query b){return a.b < b.b || a.b == b.b && a.r < b.r;}
int C2(Query a, Query b){return a.i < b.i;}
int main()
{
    int l, n, p, q, r, s = 0;
    cin >> n >> q;
    for(int i = 1; i <= n; i++)cin >> a[i];
    p = round(sqrt(n));
    for(int i = 1; i <= q; i++)
    {
        cin >> l >> r;
        query.push_back({i, l / p, l, r});
    }
    sort(query.begin(), query.end(), C1);
    l = 1;
    r = 0;
    for(auto &c: query)
    {
        for(; l > c.l; )s += a[--l];
        for(; l < c.l; )s -= a[l++];
        for(; r > c.r; )s -= a[r--];
        for(; r < c.r; )s += a[++r];
        c.s = s;
    }
    sort(query.begin(), query.end(), C2);
}

모스 알고리즘을 적용하기 위해서는 크게 두 가지 조건이 성립해야 한다.

• 원소의 변경이 없다.
• 쿼리를 원하는 순서대로 처리해도 상관 없다.

사실 첫 번째 조건이 성립하지 않으면 두 번째 조건도 성립하지 않기 때문에 두 번째 조건 하나만 성립해도 모스 알고리즘을 적용하는 데는 대부분 지장이 없다. 다만 위에서 예시로 들었던 구간 합 구하기의 경우 원소의 변경이 없으면 그냥 누적합으로 풀리는 쉬운 문제이고, 진짜로 모스 알고리즘으로 푸는 게 가장 쉬운 문제들을 연습문제에서 확인할 수 있다.

 

[연습문제]

 

BOJ 13547. 수열과 쿼리 5 (Platinum II)

구간에 존재하는 서로 다른 수의 개수를 구해야 한다. 모스 알고리즘이 사용되는 대표적인 예시인데, 각각의 $A_i$가 구간에서 나타나는 횟수를 관리하면서 풀면 된다.

 

BOJ 13548. 수열과 쿼리 6 (Platinum I)

구간에서 가장 많이 등장하는 수의 등장 횟수를 구해야 한다. 13547번의 풀이에 각 수가 몇 번씩 등장했는지를 함께 관리하는 방법을 추가하면 풀 수 있다.

 

BOJ 13704. 수열과 쿼리 11 (Platinum I)

$B_0 = 0$, $A_1$부터 $A_i$까지를 XOR한 값을 $B_i$라고 하면 주어지는 쿼리는 $l - 1 \le x < y \le r$이고 $B_x \oplus B_y = K$인 쌍 $(x, y)$의 개수를 찾는 쿼리가 된다. 역시 모스 알고리즘을 쓰면 쉽게 구할 수 있다.

 

AtCoder ABC174F. Range Set Query (1495)

앳코더에도 모스 알고리즘 쓰는 기본 문제가 나온 적이 있다. 제한이 다른 것만 제외하면 풀이는 13547번과 동일하다.

 

→ solved.ac tag: mo

---

1. 다른 알고리즘과 비교해 보면 '모 알고리즘'이라고 부르는 게 더 자연스럽다는 의견도 존재한다. 일단 한국에서는 '모스 알고리즘'이라고 가장 많이 불리는 것 같다. [본문으로]