Mo's Algorithm

Introduction

Mo's Algorithm은 구간 쿼리들을 적절한 순서로 배치해 쿼리들을 빠르게 계산하는 테크닉 입니다.

다만, 쿼리들의 순서가 바뀌다 보니, 업데이크 쿼리가 없을때만 사용 가능합니다.

이 알고리즘은 Sqrt Decomposition과 비슷한 개념이 쓰임으로, 이를 알고 보시면 좋습니다.

 

Algorithm

$s$와 $e$를 각 쿼리의 구간 시작부분과 끝 부분이라고 할 때,

 쿼리들을 $(\frac{s}{\sqrt{N}}, e)$에 대한 사전순으로 정렬 ($N$은 전체 구간의 길이)하고

순서대로 쿼리들을 계산해주시면 됩니다. (단, 두개의 포인터로 구간의 시작과 끝을 이동시키는 방식으로 계산해야됩니다)

(아래 코드를 보시면 쉽게 이해가 되실겁니다.)

 

Time Complexity

1. $e$(구간 끝)의 시간복잡도

$\frac{s}{\sqrt{N}}$가 같으면 $e$는 최대 $N$번 이동 가능하고, $\frac{s}{\sqrt{N}}$가 최대 $\sqrt{N}$번 이동 가능합니다.

그래서 $e$에 대한 총 시간복잡도는 $O(N\sqrt{N})$이 됩니다.

 

2. $s$(구간 시작 부분)의 시간복잡도

$\frac{s}{\sqrt{N}}$가 같은 경우만 고려해 주면, bucket에 의해 $s$가 움직일 수 있는 거리는 $\sqrt{N}$로 제한되고,

서로 다른 쿼리에 대해 $\frac{s}{\sqrt{N}}$가 최대 $\sqrt{N}$만큼 다를 수 있으므로,

이 경우 시간복잡도는 $O(Q\sqrt{N})$가 됩니다.

$\frac{s}{\sqrt{N}}$달라지면 $s$는 $N$만큼 추가로 이동할 수 있으므로

최종적인 $s$에 대한 시간복잡도는 $O(Q\sqrt{N} + N)$이 됩니다.

 

3. 총 시간복잡도

$e$와 $s$에 대한 시간복잡도를 합치면 $O(Q\sqrt{N} + N\sqrt{N} + N)$이지만, $N$보다 차수가 높은 항이 존재하므로

최종적으로는 시간복잡도를 $O((Q+N)\sqrt{N})$으로 나타낼 수 있습니다.

 

코드

아래 코드는 이 문제를 기준으로 작성되었습니다.

#include<iostream>
#include<algorithm>
#include<math.h>
#pragma warning(disable:4996)

using namespace std;

int sqr;
struct Query {
	int s, e, idx;

	bool operator<(const Query& c)const {
		return (s / sqr < c.s / sqr) || (s / sqr == c.s / sqr && e < c.e);
	}
};

int n, arr[100000], numCnt[1000001] = { 0 }, diffNum = 0;

int m, ans[100000];
Query query[100000];

int main(void) {
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	scanf("%d", &m);
	sqr = ceil(sqrt(1000001));

	for (int i = 0; i < m; i++) {
		scanf("%d %d", &query[i].s, &query[i].e);
		query[i].s--;
		query[i].e--;
		query[i].idx = i;
	}

	sort(query, query + m);

	int p1 = 0, p2 = -1;

	for (int i = 0; i < m; i++) {
		Query q = query[i];

		while (p2 < q.e) {
			if (numCnt[arr[++p2]]++ == 0)
				diffNum++;
		}

		while (q.e < p2) {
			if (--numCnt[arr[p2--]] == 0)
				diffNum--;
		}

		while (p1 < q.s) {
			if (--numCnt[arr[p1++]] == 0)
				diffNum--;
		}

		while (q.s < p1) {
			if (numCnt[arr[--p1]]++ == 0)
				diffNum++;
		}

		ans[q.idx] = diffNum;
	}

	for (int i = 0; i < m; i++)
		printf("%d\n", ans[i]);

	return 0;
}