모스 알고리즘
제곱근 분할법과 오프라인 쿼리를 결합한 알고리즘이다.
쿼리를 입력 순서대로 처리하지 않고, 모든 쿼리를 미리 정렬한 뒤 현재 구간의 양 끝점을 조금씩 이동하며 답을 갱신한다. 쿼리의 왼쪽 끝점을 약 $\sqrt{N}$ 크기의 블록으로 나누고, 같은 블록 안에서는 오른쪽 끝점 순서로 처리한다.
처리 순서
- 각 쿼리에 원래 순서를 기록한다.
- 왼쪽 끝점이 속한 블록을 기준으로 정렬한다.
- 같은 블록에서는 오른쪽 끝점을 기준으로 정렬한다.
- 현재 구간에 원소를 추가하거나 제거하면서 각 쿼리의 답을 계산한다.
- 답을 원래 쿼리 순서로 복원한다.
구간에 원소 하나를 추가하거나 제거하는 데 $\text{O}(1)$이 걸린다면, 전체 시간 복잡도는 일반적으로 $\text{O}((N+Q)\sqrt{N})$이다.