문제 링크

• http://icpc.me/11376

문제 링크

• http://icpc.me/11375

문제 링크

• http://icpc.me/2316

문제 링크

• http://icpc.me/9240

문제 링크

• http://icpc.me/5813

문제 링크

• http://icpc.me/2665

문제 링크

• http://icpc.me/2661

문제 링크

• http://icpc.me/5822

개요

이번 글에서는 특정 구간에 대한 쿼리를 O(√N)에 처리할 수 있는 SQRT Decomposition에 대해 알아보도록 하겠습니다.
사실 Segment Tree를 사용하면 유사한 기능을 O(log N)이라는 훌륭한 시간에 수행해낼 수 있지만, SQRT Decomposition은 다른 글에서 설명할 Mo’s Algorithm이라는 효율적인 테크닉의 기반이 되는 알고리즘으로 사용됩니다.

문제 링크

• http://icpc.me/2517