MKTHNUM - K-th Number


Tìm số bé thứ k trong đoạn i..j. Ví dụ :a = (1, 5, 2, 6, 3, 7, 4) và một câu hỏi là Q(2, 5, 3). Nghĩa là tìm số bé thứ 3 trong đoạn a[2..5]. Đáp số là 5.

Input

Dòng đầu tiên ghi n - số phần tử của mảng - và m, số truy vấn (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000). Dòng thứ hai gồm n số nguyên, có trị tuyệt đối <= 10^9. Tất cả các số đều khác nhau. Tiếp theo là m dòng,mỗi dòng có 3 số i, j, và k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j - i + 1).

SAMPLE INPUT
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Output

 
Mỗi dòng ghi kết quả của truy vấn tương ứng.

SAMPLE OUTPUT
5
6
3

hide comments
mubtasim91: 2021-01-18 22:37:18

My java code got accepted at first submission. Just merge sort tree + Binary search worked though it took over 7 seconds!

kanishkverma_1: 2020-11-24 12:37:39

Note : for java users Merge Sort Tree + BinarySearch Will give u tle on 16th Test case .

C++ same algo will work.

:(

martins_: 2020-10-15 01:31:42

Thanks for setting a Java-friendly time limit.

nemesys: 2020-10-14 15:14:27

No need for coordinade compression like some people are saying, binary searching the entire range works fine.

yaseenmollik: 2020-08-02 23:33:58

Solved using merge sort tree

tushar_ka: 2020-08-02 15:56:12

Nice problem.
There are many ways to solve this problem.
merge sort tree + binary search on array values instead of ranges: O(m * log(n)^3)
merge sort tree after index compression + binary search : O(m * log(n) ^2)
persistent segment trees : O(m * log(n))

Last edit: 2020-08-02 15:56:34
jopdhiwaala: 2020-07-18 07:40:46

I feel so bad for messing it up so many times haha

mhasan01: 2020-07-14 02:27:35

Accepted using persistent segment tree :)

aryan__0406: 2020-05-28 19:02:48

@maruf_hasan refer to geeksforgeeks article on merge sort tree and thank me later.

maruf_hasan: 2020-05-03 03:19:12

Can anybody explain how to apply the binary search on merge sort tree here?and why the binary search will work here??TIA...


Added by:~!(*(@*!@^&
Date:2009-02-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:Northeastern Europe 2004 Northern Subregion