Kth number
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12984 Accepted Submission(s): 3962
Problem Description
Give you a sequence and ask you the kth big number of a inteval.
Input
The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]
Output
For each test case, output m lines. Each line contains the kth big number.
Sample Input
1
10 1
1 4 2 3 5 6 7 8 9 0
1 3 2
Sample Output
2
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=; int T[N],num[N],san[N];
int ls[N*],rs[N*],sum[N*];
int tot,n,m;
void Update(int last,int p,int l,int r,int &rt){
rt=++tot;
ls[rt]=ls[last];
rs[rt]=rs[last];
sum[rt]=sum[last]+;
if(l==r) return;
int m=(l+r)>>;
if(p<=m) Update(ls[last],p,l,m,ls[rt]);
else Update(rs[last],p,m+,r,rs[rt]);
}
int Query(int ss,int tt,int l,int r,int k){
if(l==r) return l;
int m=(l+r)>>;
int cnt=sum[ls[tt]]-sum[ls[ss]];
if(k<=cnt) return Query(ls[ss],ls[tt],l,m,k);
else return Query(rs[ss],rs[tt],m+,r,k-cnt);
}
void work(){
int l,r,k;
for(int i=;i<=n;++i) {
scanf("%d",num+i);
san[i]=num[i];
}
tot=;
sort(san+,san+n+);
int cnt=unique(san+,san+n+)-san-;for(int i=;i<=n;++i)
num[i]=lower_bound(san+,san+cnt+,num[i])-san;
for(int i=;i<=n;++i) Update(T[i-],num[i],,cnt,T[i]);
while(m--) {
scanf("%d%d%d",&l,&r,&k);
int id=Query(T[l-],T[r],,cnt,k);
printf("%d\n",san[id]);
}
}
int main(){
int T;
for(scanf("%d",&T);T--;){
scanf("%d%d",&n,&m);
work();
}
}