MKTHNUM - K-th Number

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.

That is, given an array a[1 ... n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i ... j] segment, if this segment was sorted?"

For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2 ... 5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.


The first line of the input contains n — the size of the array, and m — the number of questions to answer (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000).

The second line contains n different integer numbers not exceeding 10^9 by their absolute values — the array for which the answers should be given.

The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j - i + 1) and represents the question Q(i, j, k).

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3


For each question output the answer to it — the k-th number in sorted 
a[i ... j] segment. 

Note : naive solution will not work!!!

hide comments
Eddy Cael: 2017-06-16 21:59:13

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

shubham: 2017-06-14 18:08:50

Qlog^3(n) doesn't work with fast input.. TLE

ksmukta: 2017-06-14 13:35:00

Did you know that naive solution of 'tourist' was accepted.

free__bird: 2017-06-12 08:35:20

took me 2 days to learn the concept of persistent tree,finally AC :) in one go.
read the tutorial of anudeep on persistent segment tree again and again and you will get the concept.
After it must try the CLONEME problem on Codechef.

barishnamazov: 2017-06-11 13:44:39

why O((n + m)log^2(n)) doesn't get tle?

mridul1809: 2017-06-08 22:44:19

persistent segment tree...amazing DS :D

sfialok98: 2017-06-06 21:16:24

Finally Accepted,Learned Persistent Segment Trees....!!!!
What a beauiful data structure..!! :-)

joseluisacv2: 2017-06-06 03:01:15

The number of queries is wrong. It is M<= 1e5

leafbebop: 2017-05-31 05:16:35

Note: sometimes it is not the algorithms blocks you from AC, but the I/O speed.
For golang user, read this topic:!topic/golang-nuts/W08rFBcHKbc
Other language may have similar issues. Try Buffered I/O.

Oh, and also, minimize function calls, of course.

Last edit: 2017-05-31 05:20:11
mddaud001: 2017-05-20 21:26:13

Trying to solve from last week
Merge sort tree + Compression + Binary_search AC :-)

Added by:~!(*(@*!@^&
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