K-th Number (NEERC 2004)

http://poj.org/problem?id=2104

https://www.acmicpc.net/problem/7469

1. Naive - O(MNlgN)

더 이상의 자세한 설명은 생략..

O(N) Selection Algorithm이 있지만 느리면 느렸지 빠르진 않을 듯.

여담으로, 잘 컷팅하면 이걸로 2번보다 빠르게 풀수 있다 ㅡㅡ;

2. Query Sorting - O(NlgN + M*N^0.5*lgN)

http://amugelab.tistory.com/entry/%EB%A3%A8%ED%8A%B8-%EC%95%BC%EB%A7%A4

때문에 역시 자세한 설명은 생략.

간단히 설명하자면, 맨 처음 좌표압축을 한 다음에 링크 1번 트릭 + K번째 원소 BIT를 구현해 주면 된다.

시간이 간당간당한 편이다.. 버킷 사이즈을 잘 잡아주고, 좌표 압축을 꼭 하자!

B = 300으로 잡으면 BOJ 1596ms, POJ 2875ms 선에서 AC를 볼 수 있다. (한쪽은 최대 시간, 한쪽은 누적 시간 기준인 걸로 암.)

Code : http://codepad.org/oY42WOkG

3. Indexed Tree and Parametric Search - O(Nlg^2N + Mlg^3N)

복잡도는 2번만큼이나 더럽지만 Query Sorting보다 빠르게 동작하는 방법이다.

이 풀이에서는 독특한 세그먼트 트리를 사용한다. 구간 [s,e]를 표현하는 노드는 a[s] ~ a[e]까지의 원소 전체를 값으로 가지고 있다. 또한, 이후 이진 탐색을 사용할 것이기 때문에 각 노드를 정렬해두자.

이는 vector 등을 통해서 쉽게 구현 가능하며, 이 때 Indexed Tree의 공간 복잡도가 O(NlgN) 임은 자명하다. 이를 정렬하는 과정은 O(Nlg^2N) 의 시간 복잡도가 소요된다.

이제 쿼리를 처리하는 부분이 문제인데 이 부분에서 Parametric Search를 사용할 수가 있다.

쿼리가 (s,e,x) (...) 로 주어진다면, 문제를 구간 [s,e] 에서 k 이하의 원소의 개수가 x개인 k를 출력하라. 라는 문제로 변형할 수 있다. 이 때 k를 이진 탐색으로 찾을 수 있다.

k 이하의 원소의 개수를 찾는 각 쿼리는, O(lgN) 개의 노드를 보며, lower_bound 등을 사용해서 O(lgN) 만에 각 노드를 처리한다. 이를 따지면 한번의 Parametric Search는 O(lg^2N) 의 시간이 걸린다는 것을 알 수 있으며, lgN 번 Parametric Search를 사용하므로, O(Nlg^2N+ Mlg^3N) 이라는 시간 복잡도에 문제를 풀 수 있다.

여담으로 이 역시 간당간당할 위험이 있으니 좌표 압축을 추천한다.

두 온라인 저지에서 아까와 완전히 극과 극의 속도를 보여서 깜짝 놀랐다.

BOJ는 224ms, POJ에서는 8547ms..

이 부분에서는 두가지 해석이 가능하다고 생각한다.

 * 1. 메모리 사용면에서 3번 풀이가 2번 풀이보다 부하가 크고, 때문에 POJ가 램이 딸려서 시간이 오래 걸렸다.

 * 2. 누적 시간을 보는 것이기 때문에, 3번 풀이는 2번 풀이보다 최대 수행 시간이 우수하지만 평균 수행 시간은 2번보다 나쁘다.

일반적인 대회 상황에서는 메모리가 빠르고, 최대 수행 시간이 우수한 풀이가 필요하기 때문에 3번 풀이가 2번 풀이보다 그냥 좋은 풀이라고 생각해도 된다.

물론, 모두 중요하고 아름다운 풀이니 익혀두어야 할 것이다.

Code : http://codepad.org/lGldUk1O

여담으로,Splay Tree를 사용하면 상당히 우수한 복잡도를 보일 수 있다고 얼핏 들었지만, 난 안 짜봐서 모름 ㅇㅁㅇ..