Sqrt Decomposition

MO's algorithm은 온라인으로 풀기 힘든 쿼리 문제를 오프라인으로 쉽게 풀 수 있게 해주는 알고리즘이다. MO's algorithm은 쿼리를 정렬한 뒤 정렬된 순서대로 처리를 한다. 이론은 이게 끝이다. 이론만 들어서는 아마 문제에 어떻게 적용해야 할 지 감이 안올것이다. 그럼 연습문제를 풀면서 MO's algorithm을 익혀보도록 하자. 연습문제는 https://www.acmicpc.net/problem/13547에서 풀 수 있다. 구간에 존재하는 서로 다른 수의 개수 연습 문제는 아래와 같다. 자연수로 이루어진 \(A_1,\ A_2,\ A_3,\ ...\ ,\ A_{N-1},\ A_{N}\)시퀀스가 있다. 이 때 다음 쿼리를 처리해야 한다. 1. \(x,\ y\ (1 \le x \le y ..

원소들을 효율적으로 관리해야할 일이 있을때 우리는 어떤 전략을 선택해야할까? 원소들을 효율적으로 관리하는 방법은 여러가지가 있다. 이번에는 그 중 하나인 Sqrt Decomposition에 대해 알아보도록 하자. Sqrt Decomposition에서 Sqrt는 Square root의 약자다. 이를 우리나라 말로 번역하자면 평방분할이라고 한다. 하지만 의미적으로 별로 와닿지 않는다고 생각하기 때문에 Sqrt Decomposition이라고 하겠다.      연속적인 원소들을 하나의 묶음으로  Sqrt Decomposition의 기본 아이디어는 정말 간단하다. 연속적인 원소들을 하나의 묶음으로 생각하자는 것이다. 이 때 한 묶음의 크기는 보통 \(\sqrt N\)으로 잡는다.(그래서 Square root라는 ..