Approach Subtree에 대한 정보를 가지고 이야기를 하고 있으므로, 오일러 투어 테크닉(ETT)를 활용하면 서브트리에 대한 정보를 쿼리 정보로 바꿔서 처리할 수 있다. 또한 추가적으로 쿼리에 대한 특정 수보다 작거나 크고 k번째 수의 경우는 머지 소트 트리를 활용해서 쉽게 풀 수 있다. 즉, 오일러 투어 테크닉(ETT)와 Mergesort Tree를 활용하면 쉽게 풀 수 있다. 느낌 자체는 https://viyoung.tistory.com/245 [백준 14287번] [세그먼트 트리 / 오일러 투어 테크닉] 회사 문화 3 Approach 가장 원초적으로 생각할 수 있는 풀이는 dfs로 계속 타고 내려가면서 계속 업데이트를 해주면 된다. 다만, 이 경우에는 시간복잡도가 $O(NM)$으로 시간이 초..

Approach 특정 구간에서 k보다 작은 개수/큰 개수는 일반적으로 머지 소트 트리를 활용해서 처리하는 경우가 많다. 머지소트가 진행되는 양상을 잘 살펴보면, 세그먼트가 구성되는 느낌이랑 거의 유사하다. 따라서 어떠한 쿼리에서 k보다 큰 개수를 구하는 과정은 다음과 같다. 1) 원하는 쿼리와 현재 탐색중인 쿼리가 전혀 교차하지 않으면 0 2) 원하는 쿼리가 현재 탐색중인 쿼리를 포함하고 있을 경우, 이진탐색하여 k보다 큰 개수를 구한다. (upper bound) 3) 겹치는 경우에는 재귀적으로 처리하면 1)과 2)의 연산의 합으로 구할 수 있다. k보다 크거나 같은/ 작거나 같은/ 작은의 경우도 비슷한 방식으로 처리해주면 된다. Code #include #define fastio ios_base::sy..