The kth number

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Do you still remember the Daming Lake's  k'th number? Let me take you back and recall that wonderful memory.

Given a sequence A with length of n,and m querys.Every query is defined by three integer(l,r,k).For each query,please find the kth biggest frequency in interval [l,r].
Frequency of a number x in [l,r] can be defined by this code:

int FrequencyOfX = 0;
for (int i = l; i <= r; i ++) {
     if (a[i]==X) {
         FrequencyOfX ++;
     }
}

Input

First line is a integer T,the test cases.
For each case:
First line contains two integers n and m.
Second line contains n integers a1,a2,a3....an.
Then next m lines,each line contain three integers l,r,k.

T<=12
1<=n,m,ai<=100000
1<=l<=r<=n
1<=k
data promise that for each query(l,r,k),the kind of number in interval [l,r] is at least k.

Output

for every query,output a integer in a line.

Sample Input

1
6 3
13 14 15 13 14 13
1 6 3
1 6 1
3 5 2

Sample Output

1
3
1

Source

zhangmingming

Manager

Information
Solved Number135
Submit Number382
Problem Tags
data structures
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel