Mo's Algorithm
BOJ 13547 문제를 기준으로 이 알고리즘을 설명하려고 한다.이 문제는 [L, R] 쿼리가 입력되면, A[L], A[L+1], ..., A[R] 중 서로 다른 수의 개수를 출력하는 것이다. Naive 한 풀이는 매우 쉬운데, 조금 덜 Naive 하게 생각해보자.즉, 이전 쿼리에 대한 답을 알고 있다는 가정 하에, 현재 쿼리는 그 변화량만 계산해서 더해주면 된다. 이전 쿼리의 L, R 을 한 칸씩 움직이면서 현재 쿼리의 L, R 쿼리로 만들어준다.이 때 숫자가 제거되거나 추가될텐데, 그에 맞게 답을 조정하는 간단한 방식이다. 하지만 이 방법 또한 O(NQ) 로 TLE가 날 것이다.Mo's Algorithm 은 오프라인 쿼리로, 이 방법을 그대로 적용하지만, 쿼리의 순서만 바꾸는 것이다.재미있는 점은,..
2022. 8. 29.
