Mo's Algorithm 의 이해와 구현

이 글에서는 BOJ 수열과 쿼리 5 문제를 해결하기 위한 Mo's Algorithm 에 대해서 설명하겠습니다.

 

Mo's Algorithm 은 update가 주어지지 않는 쿼리에서 적용할 수 있는 알고리즘으로,

가끔 세그먼트 트리로는 해결하지 못하는 문제를 해결할 수 있는 알고리즘입니다.

 

Mo's Algorithm 의 기본 아이디어는 쿼리의 순서를 원하는 대로 바꿀 수 있다는 것입니다.

update가 주어지지 않는 쿼리이므로, 원하는 순서로 배치하여 처리하고, 다시 순서를 바꾸어 출력하면 됩니다.

 

BOJ 수열과 쿼리 5 문제를 봅시다.

이 문제에서 이러한 아이디어를 생각해 봅시다.

 

cnt[x] = 지금까지 센 x의 개수, L[x]는 x번째 쿼리의 첫 번째 수, R[x]는 x번째 쿼리의 두 번째 수 일때

각 쿼리를 계산할 때 L[i] 에서 L[i+1]까지, R[i]에서 R[i+1]까지 보면서 cnt[x]를 처리해 주고, cnt[x]가 0에서 1로 바뀌면 ans++, 1에서 0으로 바뀌면 ans--를 해 줍니다.

 

이러한 처리를 통해 ans는 각 쿼리의 답이 됨을 알 수 있습니다.

하지만 시간복잡도는 O(n^2)이기 때문에 TLE가 나게 됩니다.

 

이 때 쿼리의 순서를 적절히 바꿔 줌으로써 시간복잡도를 줄일 수 있는데,

각 단계마다 L[i]에서 L[i+1]까지, R[i]에서 R[i+1]까지 움직이는 횟수를 줄여줄 수 있다면 될 것입니다.

 

Mo's Algorithm 을 이용하여 시간복잡도를 O(n*sqrt(n))으로 줄일 수 있습니다.

그 과정에 대한 직관적인 이해를 한 후에 스스로 코딩하는 것을 추천합니다.

 

이 코드에서 중요한 점은 쿼리의 순서를 바꾸는 과정에서 {L[i]/sqrtN, R[i]} 를 기준으로 정렬을 해주면

L[i], R[i]가 움직이는 횟수가 sqrtN*N이하로 줄어들 수 있다는 것고, 그것을 이용해 시간 복잡도를 줄인 것입니다.

#include<bits/stdc++.h>
using namespace std;
int N, M, L[100001], R[100001], sqrtN, cnt[1000001], ans[100001], A[1000001], ret;
vector<pair<pair<int, int>, int> > v;


int main(){
    scanf("%d", &N);
    for(int i = 1;i <= N;i++){
        scanf("%d", &A[i]);
    }
    sqrtN = sqrt(N);
    scanf("%d", &M);
    for(int i = 0;i < M;i++){
        scanf("%d %d", &L[i], &R[i]);
        v.push_back({{L[i]/sqrtN, R[i]}, i});
    }
    sort(v.begin(), v.end());
    for(int i = L[v[0].second];i <= v[0].first.second;i++) {cnt[A[i]]++; if(cnt[A[i]] == 1)ret++;}
    ans[v[0].second] = ret;
    for(int i = 1;i < M;i++){
        if(L[v[i-1].second] < L[v[i].second]){
            for(int j = L[v[i-1].second];j < L[v[i].second];j++){
                cnt[A[j]]--;
                if(cnt[A[j]] == 0) ret--;
            }
        }
        if(L[v[i-1].second] > L[v[i].second]){
            for(int j = L[v[i].second];j < L[v[i-1].second];j++){
                cnt[A[j]]++;
                if(cnt[A[j]] == 1) ret++;
            }
        }
        if(v[i-1].first.second < v[i].first.second){
            for(int j = v[i-1].first.second+1;j <= v[i].first.second;j++){
                cnt[A[j]]++;
                if(cnt[A[j]] == 1) ret++;
            }
        }
        if(v[i-1].first.second > v[i].first.second){
            for(int j = v[i].first.second+1;j <= v[i-1].first.second;j++){
                cnt[A[j]]--;
                if(cnt[A[j]] == 0) ret--;
            }
        }
        ans[v[i].second] = ret;
    }
    for(int i = 0;i < M;i++) printf("%d\n", ans[i]);
    return 0;
}