개요

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

문제 링크

• http://icpc.me/2517

문제 링크

• http://icpc.me/16986

문제 링크

• http://icpc.me/16985

문제 링크

• http://icpc.me/13310

문제 링크

• http://icpc.me/2473

문제 링크

• http://icpc.me/2162

문제 링크

• http://icpc.me/10216

문제 링크

• http://icpc.me/16975

문제 링크

• http://icpc.me/4792