Introduction Sqrt Decomposition이란 구간을 $\sqrt{n}$개의 bucket으로 나눠 쿼리를 $O(\sqrt{n})$ 만에 처리하는 테크닉이다. 물론 세그먼트 트리를 이용하면 $O(\log{n}) $만에 구간 쿼리를 계산할 수 있지만, Sqrt Decomposition 은 Mo's Algorithm에 기반이 된다고 하니 배워보자. 코드 아래의 코드는 이 문제를 기준으로 작성되었다. #include #include #include using namespace std; const int MAX = 1000000001, MIN = 0; struct Ele { int min, max; }; int n, m, sqr; Ele arr[100001], bucket[400]; inline E..

Master Theorem을 이용하면 재귀적인 구조를 갖는 알고리즘의 시간복잡도를 간단하게 계산할 수 있다. 알고리즘이 시간복잡도 $T(n) = aT(\frac{n}{b}) + O(n^k)$ 으로 표현될때, $T(n)$ 은 다음과 같이 계산할 수 있다. $$ \begin{align} &1. \; a>b^k \quad \Rightarrow \quad T(n) = O(n^{log_{b}{a}})\\ &2. \; a=b^k \quad \Rightarrow \quad T(n) = O(n^k log n)\\ &3. \; a

Introduction 단절점이란 제거했을때 연결되어있던 그래프가 둘 이상으로 나눠지는 그래프를 말한다. 단절점을 가장 naive 하게 구하는 방법은 모든 정점에 대해 그 정점을 제거할 경우 connected component가 증가하는지를 탐색을 통해 확인하면 된다. 이 경우 시간복잡도는 $O(V^2)$ 가 된다. 하지만 단절점의 특징을 사용해서 탐색 한번으로 $O(V)$ 단절점을 구할 수 있다. 단절점 구하기 아래 그림을 보자. 위 그림은 root를 시작점으로 dfs를 도는 중간 과정을 나타낸다. 빨간색 정점 : 현재 보고있는 정점이다. 검은색 간선 : 바로 직전에 타고(?) 온 간선으로 root 쪽에서 왔다는것을 나타낸다. 보라색 정점 : root 쪽에서 이미 탐색을 완료한 정점이다. 파란색 덩어리..