오프라인 쿼리를 제곱근 분할법을 사용하여 빠르게 처리하는 알고리즘.

제약 조건

---

크기가 $N$인 입력 배열 $Arr$과 $Q$개의 쿼리가 있다. 각 쿼리는 $[L, R]$로 표현된다. ($L \le R$)

1. $Arr$은 쿼리에 의해 변경되지 않고, 모든 쿼리들은 사전에 정보가 주어진다. (오프라인 쿼리)
2. $[L,R]$을 계산한 이후, 범위가 1만큼 차이나는 쿼리(e.g. $[L+1,R], [L, R-1]$)들을 일정 시간(e.g. $O(F)$)에 구한다.
   
   
   

정의

---

1. 모든 인덱스는 0부터 시작한다.
2. $BLOCK\_SIZE = \lfloor\sqrt{N}\rfloor$
3. 어떤 쿼리 $[L, R]$는 $\lfloor L / BLOCK\_SIZE \rfloor$번째 블록에 속한다.
4. 같은 블록에서는 $R$이 작을 수록 우선순위가 높다. 즉, [4,8]보다 [4,6]이 먼저 처리된다.
5. 블록의 개수 $k = \lceil N/BLOCK\_SIZE \ \rceil$
6. $B_i$ : $i$번 블록.
7. $|B_i|$ : $i$번 블록에 속한 쿼리의 개수
   
   
   

시간 복잡도

---

$O(Q\log Q + (N+Q)\sqrt{N}F)$

모스 알고리즘은 $B_0$부터 $B_{k-1}$까지 우선 순위에 따라 쿼리들을 처리한다. 따라서 각 블록들을 우선순위에 따라 정렬한다 : $O(Q\log Q)$

모스 알고리즘은 이전에 처리한 쿼리의 범위를 활용한다. 즉, 좌측 값과 우측 값을 최소한으로 증감하여 쿼리들을 처리한다. 좌/우측 값이 총 $O((N+Q)\sqrt{N})$만큼 변화하고, 좌/우측값이 1 변화할 때마다 $O(F)$시간이 소요된다 :
$O((N+Q)\sqrt{N}F)$

우측 값($R$)의 변화

1. 블록 안에서

   한 블록에서 $R$은 증가하기만 한다. $R$은 $N$보다 커질 수 없다. 따라서 한 블록에서 $R$은 $O(N)$만큼 바뀐다. 블록은 $O(\sqrt{N})$개 있으므로, 총 $O(N\sqrt{N})$으로 계산할 수 있다.

2. 블록이 바뀔 때

   블록이 바뀌는 순간에 $R$은 최대 $N-1$만큼 바뀐다. 블록은 $O(\sqrt{N})$번 바뀌므로, 총 $O(N\sqrt{N})$으로 계산할 수 있다.

알고리즘 수행 중 우측 값의 변화는 1, 2를 합쳐 총 $O(N\sqrt{N})$만큼이다.

좌측 값($L$)의 변화

1. 블록 안에서

   같은 블록에서 $L$은 최대 $\sqrt{N}$만큼 차이난다. 따라서 어떤 블록 $B_i$에서 $L$은 $O(|B_i| * \sqrt{N})$만큼 바뀐다.
   $|B_0| + |B_1| + ... + |B_{k-1}| = Q$이므로, 총 $O(Q\sqrt{N})$으로 계산할 수 있다.

2. 블록이 바뀔 때

   어떤 블록 $B_i$에서 다른 블록 $B_{i+x}$ $(x > 0)$로 갈 때 $L$은 $O(x * BLOCK\_SIZE)$만큼 바뀐다. 블록이 $k$개 있으므로 모든 $x$의 합이 $k$를 넘을 수 없다. 따라서 총 $O(k*\sqrt{N}) = O(\sqrt{N} * \sqrt{N}) = O(N)$으로 계산할 수 있다.

알고리즘 수행 중 좌측 값의 변화는 1, 2를 합쳐 총 $O(Q\sqrt{N} + N)$이다.

연습문제

• 백준 13547

참고 자료

https://www.hackerearth.com/practice/notes/mos-algorithm/