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
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

devarshi09: 2018-05-03 06:15:15

O(log N)^3 works fine!
Solved with Merge Sort tree!

Jose Arias Perez [KIR@]: 2018-03-05 02:17:42

Any tips on the MergeSort solution with O(lg^2N) per query ??

siva2697: 2018-03-03 08:53:34

size of seg tree =2060964 AC :)

sarwar__05: 2017-12-19 13:56:43

Solve KQUERYO first.

Last edit: 2017-12-19 13:57:07
newbie: 2017-10-24 22:26:38

finally accepted,
A few tips:
1. numbers can be +ve, -ve and 0.
2. Use Fast I/O Got many tle because of that.

Thanks to @harsh_jain1 for giving the hint that it can be solved using trie also.

AAKASH TYAGI: 2017-08-13 21:29:57

O( log^3 n ) per query works fine. Just remember to binary search on array elements rather than the entire range.

harsh_jain1: 2017-08-10 19:43:35

Solved using trie...wow!!

nikolatech: 2017-06-24 12:52:52

Last edit: 2018-02-21 13:49:34
Eddy Cael: 2017-06-16 21:59:13

Hint: Maybe you will need to solve KQUERY first. using Segment Trees of course.


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