Kth number |
| Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 37 Accepted Submission(s): 25 |
|
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] |
|
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 |
|
Source
HDU男生专场公开赛——赶在女生之前先过节（From WHU）
|
|
Recommend
zty
|
/*---------------------------------------------- File: Date: 2017/6/9 21:40:22 Author: LyuCheng ----------------------------------------------*/ #include <bits/stdc++.h> #define MAXN 100005 using namespace std; int t,n; int q,l,r,k; /************************************划分树模板************************************/ int a[MAXN]; //原数组 int sorted[MAXN]; //排序好的数组 //是一棵树，但把同一层的放在一个数组里。 int num[20][MAXN]; //num[i] 表示i前面有多少个点进入左孩子 int val[20][MAXN]; //20层,每一层元素排放，0层就是原数组 void build(int l,int r,int ceng) { if(l==r) return ; int mid=(l+r)/2,isame=mid-l+1; //isame保存有多少和sorted[mid]一样大的数进入左孩子 for(int i=l;i<=r;i++) if(val[ceng][i]<sorted[mid]) isame--; int ln=l,rn=mid+1; //本结点两个孩子结点的开头，ln左 for(int i=l;i<=r;i++) { if(i==l) num[ceng][i]=0; else num[ceng][i]=num[ceng][i-1]; if(val[ceng][i]<sorted[mid] || val[ceng][i]==sorted[mid]&&isame>0) { val[ceng+1][ln++]=val[ceng][i]; num[ceng][i]++; if(val[ceng][i]==sorted[mid]) isame--; } else { val[ceng+1][rn++]=val[ceng][i]; } } build(l,mid,ceng+1); build(mid+1,r,ceng+1); } int look(int ceng,int sl,int sr,int l,int r,int k) { if(sl==sr) return val[ceng][sl]; int ly; //ly 表示l 前面有多少元素进入左孩子 if(l==sl) ly=0; //和左端点重合时 else ly=num[ceng][l-1]; int tolef=num[ceng][r]-ly; //这一层l到r之间进入左子树的有tolef个 if(tolef>=k) { return look(ceng+1,sl,(sl+sr)/2,sl+ly,sl+num[ceng][r]-1,k); } else { // l-sl 表示l前面有多少数，再减ly 表示这些数中去右子树的有多少个 int lr = (sl+sr)/2 + 1 + (l-sl-ly); //l-r 去右边的开头位置 // r-l+1 表示l到r有多少数，减去去左边的，剩下是去右边的，去右边1个，下标就是lr，所以减1 return look(ceng+1,(sl+sr)/2+1,sr,lr,lr+r-l+1-tolef-1,k-tolef); } } /************************************划分树模板************************************/ int main(int argc, char *argv[]){ // freopen("in.txt","r",stdin); scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++){ scanf("%d",&val[0][i]); sorted[i]=val[0][i]; } sort(sorted+1,sorted+n+1); build(1,n,0); while(q--){ scanf("%d%d%d",&l,&r,&k); printf("%d ",look(0,1,n,l,r,k)); } } return 0; }