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

Added by:psetter
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

hide comments
2024-10-09 07:44:01
coordinate compresion + partition segmentree
2023-10-20 23:16:08
Some (maybe all) of the input test cases use '\r\n' , watch out for that. Also the array elements can be negative in input tests, watch out for that too.
2023-10-03 11:09:02
we dont need merge sort just use quick sort and segment tree you will get AC
2023-09-14 00:03:05
merge sort tree is giving me TLE in C++. - _ -
2023-06-09 13:55:40
is there any test cases which could be giving me a WA, all my test cases that I tried seem correct
2023-05-07 17:32:41
DANG ! I just bought the Darth Vader skin in Fortnite ! I am cool now
2023-01-04 11:09:52
used wavelet tree and array value compression . got accepted , time taken 1s
2022-12-13 10:15:04
O(nlogn + mlog(2e9)lognlogn)
2022-11-28 19:39:50
@fire5386 how the hell, its not working and won't work
2022-09-02 10:59:26
O(NlogN + QlogN) using Persistent Segment Tree
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.