[BOJ] 7469 : K번째 숫자
7469 : K번째 숫자 풀이 구간합 트리를 쫌 변형해보자. 구간합 트리는 [lft, rgt] 구간에 있는 원소들의 합을 관리한다. 여기서! 원소들의 합을 원소들로 바꿔서 관리해주자! 노드를 int: 구간합이 아니라 vector: 구간의 원소들로 관리하는 거다. 구간을 실체화 시켰다고 하면 될라나? 노드가 2*n개이므로 메모리는 O(n log n)으로 충분하다! 이제 각각의 벡터에는 [lft, rgt] 구간의 원소들이 들어있게 되었고, 이제 각각의 벡터를 정렬해주자. 그리고 쿼리가 들어오면, [s, e] 구간에서 x번째 수가 무엇인지 찾아낼 것이다. 그 수를 이분탐색으로 찾아줄 건데 이건...