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
golu20174024: 2019-03-21 03:47:47

use persistent segment tree and i-th order statistics

ab_biswas09: 2019-03-16 20:11:15

Finally AC

kukreja_vlk: 2019-03-09 04:27:35

Any solutions in Java ? Getting TLE after some cases

gormint7777: 2019-03-05 19:21:50

weak test cases!!

nik7: 2019-02-18 06:42:01

@newbie how it can be solved using trie. Can you please explain

alucard_01: 2018-12-19 15:04:12

cool sum..!!

kspoj: 2018-12-07 18:23:11

My first persistent seg tree prob.. Yay :D

tien0903: 2018-11-22 12:31:34

awesome problems =)) and very nice persistant IT too . it's a amazing :v

rituraj2847: 2018-09-05 14:14:33

Print '-1' if there's no kth number.

kkislay20: 2018-07-02 09:22:38

I am getting TLE..could someone help me out https://ideone.com/v9UzfI
I used merge sort with O(N*2 (logn)*2 ) sol


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