pst1 BOJ 7469 - K번째 수 ( 머지소트트리, pst ) https://www.acmicpc.net/problem/7469 두가지 방법으로 가능 머지소트트리, 퍼시스턴트세그트리 pst론 구간 k번째 수를 효과적으로 셀 수 있다. (세그먼트트리에서 전체 k번째 수를 세는 것이랑 비슷함) 최대 1e5개의 정수 배열이 주어진다. 배열의 원소는 절대값이 1e9보다 작은 정수이다. 다음 쿼리를 처리 s,e,k : 구간[s,e]의 k번째 수를 출력 - 머지소트트리 머지소트트리를 만든 후, 1. 쿼리마다 -1e9~1e9사이에서 k번째 수가 될 수 있는 최소값을 구한다. 구간에서 x미만의 수의 개수가 k-1개이상인 수 중 최소값을 구해주면 된다. (이분탐색 시 음수범위에 주의) 2. 구간에서 x이상 최소값을 찾아 출력해준다. const int MAX = 2e5 + 4; co.. 2020. 6. 10. 이전 1 다음