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
piasroy071: 2019-10-21 20:11:07

Somehow my solution of merge sort tree with O(log^3 * N) got AC in 1.04s, although the time limit is 0.115s-0.667s. Can someone explain this?
Submissions: https://www.spoj.com/status/MKTHNUM,piasroy071/

zhaopeng: 2019-05-20 12:25:28

Merge Seg + Binary Search + compress(TLE if without), AC.
for each query, many said O(lg^3 N). I believe it's amortized O(lg^2 N). 1(BS) + 1(segment), and should not be another 1, since total size of segments ~ N.

caro_linda2018: 2019-04-26 02:16:28

ACed it in one go :)

Last edit: 2019-04-26 02:17:03
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


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