K번째 수

• 구간 k-th 쿼리 문제.
• 구간 k-th 쿼리에서 설명했듯 이 문제에 사용가능한 방법이 몇가지 있다. 자세한 설명은 링크를 참조하고, 실제 이 문제에 적용한 결과는 아래와 같았다.
  • 구간압축을 안한 PST : 2164ms (시간복잡도: O(nlogm + qlogm))
  • 구간압축을 한 PST : 1380ms (시간복잡도: O(nlogn + qlogn))
  • 머지소트트리 + 바이너리서치 : 1116ms (시간복잡도: O(nlogn + qlog^3(n)))
  • 인덱스로 만든 머지소트트리 : 452ms (시간복잡도: O(nlogn + qlog^2(n)))
• 아래에 첨부한 코드는 '인덱스로 만든 머지소트트리' 방법이다.

"""Solution code for "BOJ 7469. K번째 수".

- Problem link: https://www.acmicpc.net/problem/7469
- Solution link: http://www.teferi.net/ps/problems/boj/7469
"""

import bisect
import operator
import sys


class MergeSortTreeForKthElem:
    def __init__(self, values):
        l = [[i] for i, value
             in sorted(enumerate(values), key=operator.itemgetter(1))]
        self._values = values
        self._size = 1 << (len(l) - 1).bit_length()
        self._tree = ([[] for _ in range(self._size)]
                      + l + [[]] * (self._size - len(l)))
        for i in range(self._size - 1, 0, -1):
            self._tree[i] = self._tree[i * 2] + self._tree[i * 2 + 1]
            self._tree[i].sort()

    def kth(self, beg: int, end: int, k: int) -> int:
        i = 1
        while i < self._size:
            i += i
            node = self._tree[i]
            t = bisect.bisect_left(node, end) - bisect.bisect_left(node, beg)
            if t < k:
                k -= t
                i += 1
        return self._values[self._tree[i][0]]


def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    nums = [int(x) for x in sys.stdin.readline().split()]
    mst = MergeSortTreeForKthElem(nums)
    for _ in range(m):
        i, j, k = [int(x) for x in sys.stdin.readline().split()]
        print(mst.kth(i - 1, j, k))


if __name__ == '__main__':
    main()