Mo's 알고리즘

Mo's 알고리즘이란

배열에 대한 여러 구간 질의 \([l, r]\)를, 현재 구간을 양 끝에서 한 칸씩 넓히고
좁히며 답을 갱신하는 오프라인 기법이다. "구간 안 서로 다른 수의 개수", "구간
원소 빈도의 제곱 합" 등 점진적으로 갱신 가능한 질의에 강력하다.

전제는 다음 네 연산을 각각 \(O(1)\)(또는 충분히 싸게)에 할 수 있다는 것이다.

• add(x): 현재 구간에 원소 \(x\)를 추가하며 답 갱신.
• remove(x): 현재 구간에서 원소 \(x\)를 제거하며 답 갱신.

오른쪽 끝을 \(+1\)/\(-1\), 왼쪽 끝을 \(+1\)/\(-1\) 움직이는 네 가지로 임의의 구간으로
이동할 수 있다.

왜 블록 정렬인가

질의를 임의 순서로 처리하면 포인터가 마구 움직여 총 이동량이 \(O(NQ)\)가 될 수
있다. Mo는 인덱스를 크기 \(B\)의 블록으로 나누고, 질의를 다음 기준으로
정렬한다.

\(l\)이 속한 블록 번호를 1순위, \(r\) 을 2순위로 정렬.
(블록이 짝수면 \(r\) 오름차순, 홀수면 내림차순으로 두면 더 빠르다 — 지그재그.)

이렇게 하면 포인터 이동량을 분석적으로 묶을 수 있다.

복잡도 분석

• 오른쪽 포인터 \(r\): 같은 블록 안의 질의들끼리는 \(r\)이 단조이므로 한 블록
  안 이동이 \(O(N)\). 블록이 \(N/B\)개라 총 \(O(N^2 / B)\).
• 왼쪽 포인터 \(l\): 같은 블록 안에서 \(l\)은 블록 크기 \(B\) 안에서만 움직이고
  질의가 \(Q\)개이므로 총 \(O(QB)\).

합 \(O(N^2/B + QB)\)를 \(B\)로 최소화하면 \(B = N / \sqrt{Q}\)에서 최솟값
\(O((N + Q)\sqrt{N})\), 흔히 \(O((N+Q)\sqrt N)\)로 적는다(\(\approx N \approx Q\)
가정). 블록 크기 선택이 성능에 직결되므로 보통 \(B = N / \sqrt{Q}\)나 단순히
\(\sqrt N\)을 쓴다.

한계와 변형

• 점 갱신이 섞이면 시간 차원을 추가한 Mo with updates(3차원 정렬,
  \(O(N^{5/3})\))를 쓴다.
• 트리 경로 질의는 오일러 투어로 펼쳐 트리에서의 Mo로 변형한다.
• add/remove가 무거우면(예: \(O(\log N)\)) 그만큼 곱해진다. 가능하면 \(O(1)\)
  갱신을 설계하는 것이 핵심이다.

Mo는 "갱신 가능한 구간 통계"를 자료 구조 없이 정렬만으로 처리하는 우아한
오프라인 도구다.

Mo's 알고리즘 구현 (서로 다른 수의 개수)

cnt[v] = 현재 구간 내 값 \(v\)의 등장 횟수, cur = 현재 답.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
int n, q, a[MAXN], cnt[1000001], cur = 0, ans[MAXN];
int BLOCK;

struct Query { int l, r, idx; };

void add(int v)    { if (cnt[v]++ == 0) cur++; }   // 처음 등장하면 종류 +1
void remove_(int v){ if (--cnt[v] == 0) cur--; }   // 마지막이 빠지면 종류 -1

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &q);
    vector<Query> Q(q);
    for (int i = 0; i < q; i++) {
        scanf("%d %d", &Q[i].l, &Q[i].r);
        Q[i].l--; Q[i].r--; Q[i].idx = i;          // 0-indexed
    }
    BLOCK = max(1, (int)(n / sqrt(q + 1)));
    sort(Q.begin(), Q.end(), [&](const Query& a, const Query& b) {
        int ba = a.l / BLOCK, bb = b.l / BLOCK;
        if (ba != bb) return ba < bb;
        return (ba & 1) ? (a.r > b.r) : (a.r < b.r); // 지그재그
    });

    int curL = 0, curR = -1;            // 현재 구간 [curL, curR]
    for (auto& query : Q) {
        while (curR < query.r) add(a[++curR]);
        while (curL > query.l) add(a[--curL]);
        while (curR > query.r) remove_(a[curR--]);
        while (curL < query.l) remove_(a[curL++]);
        ans[query.idx] = cur;
    }
    for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
    return 0;
}

포인터 이동 순서 주의

네 개의 while 순서는 항상 넓히기(add)를 먼저, 좁히기(remove)를 나중에
두는 것이 안전하다. 위 순서(R 확장 → L 확장 → R 축소 → L 축소)를 지키면
구간이 일시적으로 음수 길이가 되어 같은 원소를 중복 제거하는 사고를 피한다.

흔한 실수

• 이동 순서 뒤바꿈 — remove를 먼저 하면 curL > curR인 빈 구간에서
  존재하지 않는 원소를 제거해 cnt가 음수가 된다. 확장을 먼저 하라.
• 블록 크기 — 너무 작거나 크면 느리다. \(n / \sqrt q\) 근처가 보통 최적.
• 0/1-indexed 일관성 — 입력을 0-indexed로 바꿨다면 모든 비교를 거기에
  맞추자.
• 무거운 add/remove — 갱신이 \(O(1)\)이 아니면 복잡도에 곱해진다. 빈도
  배열로 \(O(1)\) 갱신이 가능한 형태로 문제를 환원하는 것이 핵심.

응용 패턴

Mo는 정렬과 두 포인터만으로 복잡한 구간 통계를 처리하는 오프라인 사고의
정점이다. 갱신·트리·시간 차원으로의 확장까지 익히면 적용 범위가 매우 넓어진다.