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

[Edited by EB]
M <= 5000 is true.

Last edit: 2017-09-02 01:23:22
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 :-)

rihaz_zahir: 2017-02-15 20:12:33

why array compression with sqrt decomposition + segment tree is giving tle?

crazymax: 2016-10-31 15:01:26

Mo+ordered_set_tree (complexity with - Q*sqrt(N)*log(N)+N*sqrt(N)) solution gives TLE. :(

Ravi kumar: 2016-10-25 15:57:06

Increase time limit for java. there is not even a single accepted solution.
using (n+m)*logn complexity algo.

Edit: i tried the same algo in C++ and it passed. you need to increase time limit for java.

Last edit: 2016-10-25 16:17:58

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