트리를 만들 때는 트리 높이가 H=logN이고 깊이가 h인 칸엔 노드가 2^h개이고 각 노드가 값 2^(H-h)개를 가지므로

깊이가 h인 칸의 총 값 개수는 h에 상관없이 모두 똑같이 2^h*2^(H-h)=2^H=N개일 것입니다. (편의상 N = 2^H라 가정합시다)

각 칸의 왼쪽/오른쪽 자식의 원소들을 머지소트 하듯이 합쳐서 정렬된 원소를 갖추는 데 선형 시간, 즉 원소 개수의 시간이 걸리므로

층마다 병합에는 총합 O(N)의 시간이 걸리고 층이 logN개이므로 트리를 만드는 데는 실질적으로 O(NlogN)의 시간이 듭니다.

실제로 머지소트를 하는 복잡도와 같죠. 잘은 모르겠지만 트리를 만드는 부분에서는 시간초과가 나진 않으신 것 같구요...

사실 검색하는 부분이 문제입니다. k번째 수를 찾는 연산을 구현하기는 어렵고,

쿼리를 Q'(i, j, x): 구간 [i, j]에서 x보다 작은 수의 개수로 변형시켜서 x를 갖고 이분 탐색을 해서 x보다 작은 수가 k개인 x를 찾아야 합니다.

x보다 작은 수의 개수를 세는 것은 각 노드에서 역시 바이너리서치를 하면 어렵지 않게 구현할 수 있습니다.

시간복잡도는 굉장히 복잡하긴 한데, 각 노드에서 이분탐색을 하는 데 평범한 연산 O(1)보다 큰 O(logN)이 소요되지만

한 번의 쿼리에는 O((logN)^2)가 소모되고 Q' 쿼리 자체도 이분탐색을 해야 하니 log(10^10)번이 곱해져 삼중 로그 시간복잡도가 됩니다.

쿼리가 M개(M<=5000)이므로 O(M*(logN)^2*(log10^10))의 시간이 필요한데 시간 안에 작동이 됩니다.

사실 저도 인터넷에서 다른 고수분들의 글을 보고 구현한 것이고 아마 그분들 중 한 분이 이전 글에 댓글도 다셨던 것 같네요.

http://koosaga.myungwoo.kr/entry/Kth-Number-NEERC-...

제가 참고하였던 글은 이것입니다 ㅋㅋ 여기서 3번 방법을 행하고계신것 맞죠?

@kks227 자세한 설명 정말 감사드립니다. 궁금한것이 두가지가있습니다.

첫번째는 제가 위의 소스코드에서 구현한 query 함수의 시간복잡도도 init 과 같다고 생각하는데 단순히 M 번의 쿼리를 돌리기 때문에 TLE 가 나는것인가요?

그리고 두번째는 링크를 들어가보니 parametric search 를 사용한다고 되어있는데, 우선 logN 개의 노드를 확인하고 각각의 노드에서 binary search 로

한번의 쿼리(L,R,x) 로 (L,R) 구간에서 x 보다 작은 원소의 개수를 O(lg^2N) 으로 구할 수 있다는 것은 알겠습니다. 하지만 구간 (L,R) 에서 총 R-L+1 개의 원소에 대해서

순차적으로 쿼리를 돌리면 O(N) 가 걸리기 때문에 AC 되지 못할테고 구사과님 블로그에선 parametric search 를 통해 O(lgN) 로 쿼리를 돌린다고 되어있는것같은데

이 부분이 이해가 가지않습니다..ㅠㅠ 감사합니다

매 query의 시간복잡도가 init과 같다면 init의 시간복잡도가 O(NlogN)이었으니

쿼리 M번이면 O(MNlogN)으로 시간초과가 맞네요.

두 번째의 경우 세그먼트 트리의 구조상 구간 (L, R)에 대해서 R-L+1개의 원소 각각에 쿼리를 돌릴 일은 절대 없다고 볼 수 있을 듯 합니다.

세그먼트 트리의 구조상 계속 자식 정점들의 결과를 구해서 합치는 중에, 만약 어떤 정점이 관장하는 구간이 (L, R)에 완전히 속해 있다면 그 자식 정점들의 결과를 묻지 않고 바로 자신의 값을 리턴해버리기만 하면 되기 때문입니다.

예를 들어 N=8이고 전체 구간이 [0, 7]일 때, 구간 [1, 6]의 결과를 보고 싶다면

맨 처음엔 루트[0, 7]가 자신의 양쪽 자식 결과를 합치려고 할 겁니다. 따라서 [0, 3]과 [4, 7]이 불러집니다.

[0, 3]은 또 [0, 1]과 [2, 3]을 부르게 되는데, 이때 [2, 3]은 구간 [1, 6]에 완전히 포함되므로 따로 결과를 구할 필요없이 자신의 값을 리턴해버립니다.

이런 식으로 아래로 내려가면서 실질적으로 호출되는 재귀함수의 수가 기하급수적으로 줄어들게 되는데,

원래 구간 자체가 선형이라서 이 구간의 일부는 포함하지만 이 구간에 완전히 포함되지는 않는 disjoint한 구간을 3개 이상 만들 수가 없습니다.

그래서 각 깊이마다 새로 재귀 호출을 하는 구간 노드는 2개 이하가 돼서, 결국 최대 재귀호출 횟수는 2*logN번 근처라고 추측할 수 있습니다. O(logN)이라 봐도 무방하죠.

지금까지의 경우는 평범한 세그먼트 트리들인 구간 합, 구간 최댓값 같은 트리의 이야기였는데 여기서는 각 노드가 자신의 값을 가지고 있기 때문에 단순히 O(1)만에 리턴만 해주면 되고,

이 문제의 경우는 한 노드의 값 자체가 원소 여러 개인 리스트라서 처리할 연산이 좀 필요해 O(logN)이 더 소모되지만 시간초과까지 이르지는 않습니다.

@kks227 음 약간 의미가 잘못 전달 되었던것같은데 제가 말한 (L,R) 은 세그트리 에서의 구간이 아니라 처음에 입력받은 배열에서의 구간을 말씀드린겁니다!

배열에서의 구간에 특정 수를 x 값으로 해서 (i,j,x) 쿼리를 돌리면 이 수가 구간내의 수들을 정렬했을때 몇번째로 작은 수인지를 O(lg^2n) 의 복잡도로 찾을 수 있다는것까지는 이해가된것같은데

이걸 어떻게하면 O(lgN) 만에 이 구간내에서 K 번째인 숫자를 찾아낸다는건지 이해가안갑니다! 여기서 parametric search 라는걸 쓰는건가요? 정확히 어떻게 동작하는지 설명해주시면 감사드리겠습니다.

아하... 제가 이해를 잘못했군요 ㅠㅠ

일단 parametric search는 주어진 문제의 답이 뭔지는 모르겠고 일단 아무거나 찔러넣어봐서 추측하는 겁니다.

예를 들면 k^2 >= 11인 최소의 k를 이 방식으로 찾고 싶다고 할 때,

k=1을 시도해봤더니 아닙니다. 1은 답이 아닙니다. k=2도, k=3도 아닙니다.

그런데 k=4를 시도해봤더니 조건이 맞아떨어졌고, k=1~3은 k^2 >= 11이 아니었으므로 최소의 k는 4라는 걸 알게 됩니다.

물론 이렇게 하나하나 1 증가시키면서 던져보면 선형 시간이 걸리지만, 여기서 중요한 사실은

답 k가 있을 때, k보다 작은 모든 수 i에 대해 i^2 >= 11이 성립하지 않고, k 이상의 모든 수 j에 대해 j^2 >= 11이 성립한다는 사실입니다.

k가 구간을 딱 만족/불만족 2개의 구간으로 양분하고 있는 것이죠.

그래서 이 k를 이분 탐색으로 찾을 수 있습니다. (문제에 따라 다른 형태의 탐색을 사용하는 경우도 있습니다. 삼분 탐색이라던가...)

구간 [lo, hi]를 잡았을 때 lo는 조건을 불만족하는 값이고 hi는 조건을 만족하는 값이라 할 때, lo<k<=hi가 반드시 성립함을 알 수 있고

따라서 mid=(lo+hi)/2를 피벗으로 두고 mid가 조건을 만족하는지 검사하여 조건을 만족하면 구간을 [lo, mid]로, 불만족하면 [mid, hi]로 줄여나가는 식입니다.

이렇게 해서 lo와 hi의 차가 1이 되면 hi가 만족하는 최소의 값임을 알 수 있게 됩니다.

매번 구간이 반씩 줄어드므로 탐색 횟수는 처음 구간 크기를 N이라 하면 O(logN)번 이루어짐도 알 수 있구요.

매번 결과 판단하는 시간이 O(1)이었으므로 parametric search 전체엔 O(1)*O(logN) = O(logN)이 걸렸습니다.

결과 판단에 O(f(N))의 시간이 걸린다면 전체 O(f(N)*logN)일 것입니다.

이걸 이 문제에 적용합니다. 말씀하신 대로 여기서 parametric search를 사용하여 K번째 수를 찾을 수 있습니다.

만약 Q'(i, j, x) >= K라면 K번째 수는 x보다는 작을 겁니다. x보다 작은 수가 이미 K개나 되기 때문에 x 이상의 원소는 K번째 수가 될 수 없습니다.

반면에 Q'(i, j, x) < K라면 K번째 수는 x 이상일 겁니다. x보다 작은 수가 K-1개 이하이므로 x는 K번째 수거나 그보다 앞의 수겠죠.

우리가 찾고 싶어하는 것은 Q'(i, j, x) == K-1인 x이고, 이 x를 이분 탐색을 가미한 parametric search로 찾을 수 있습니다.