20190728

[Algorithm] Mo’s Algorithm

출처

Mo’s Algorithm (Query square root decomposition)
link 1 link 2 link 3
활용 예는 얼마 안되지만 몇 가지 어려운 자료구조 문제에 적용 가능하다.
예시 1) 크기 N 의 배열 a[] 가 있을 때, a[l..r] 부분 배열에서 가장 많이 출현하는 값을 구하시오.
예시 2) 크기 N의 배열 a[]에서 a[l..r] 부분 배열에서 3번 이상 출현하는 값의 개수를 구하시오.
세그먼트 트리나 기타 다른 자료구조를 사용할 수도 있지만 l..mid, mid+1..r 범위에서 정답을 안다고 해도 l..r 에서의 답을 구하는 것이 어렵다. (병합이 어려움)

시간복잡도

(분석은 생략)
O(QlogQ + Nsqrt(N)logN)

사용

M개의 쿼리가 주어진다면, M개의 쿼리를 재배열 해서 사용하는 offline 알고리즘이다. 각각의 쿼리에 L, R 이 주어진다. 우선, 입력 받은 배열을 sqrt(N) 개 블록으로 나눈다. 각각의 블록은 N/sqrt(N), 즉 sqrt(N) 크기를 가진다. 쿼리의 L과 R은 이 블록 중 하나에 포함될 것이다.
만약에 P’ 블록에 L이 들어있다면 쿼리의 범위는 P’ 블록에 속할 것이다. 받은 모든 쿼리들을 속하는 블록 번호 오름차순으로 정리한다. R 또한 어느 블록에 속하게 될 것이다. R에 대해서도 정렬한다. (즉, L/sqrt(N), R 을 기준으로 오름차순 정렬)

(정렬 코드는 생략)

이제 정렬한 쿼리들을 가지고 문제를 풀면 된다. 첫 번째 쿼리는 직접 구하고, 이 쿼리를 바탕으로 두 번째 쿼리로 확장 축소하며 구해가면 된다.
확장 축소 하는 시간 복잡도는 O((|l-l’| + |r-r’|) * logN)