Kth number
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2301 Accepted Submission(s): 782
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
Source
Recommend
zty
时间复杂度O(
空间复杂度O(
#include<stdio.h> #include<algorithm> using namespace std; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define MAXN 110000 int sorted[MAXN]; int val[20][MAXN]; int toL[20][MAXN]; int n,m; void build(int l,int r,int rt,int d) { if(l==r) { return ; } int i,count,mid=(l+r)>>1; int tmp=sorted[mid]; count=mid-l+1; for(i=l;i<=r;i++) { if(val[d][i]<tmp) count--; } int lpos=l,rpos=mid+1; toL[d][0]=0; for(i=l;i<=r;i++) { if(val[d][i]<tmp) { val[d+1][lpos++]=val[d][i]; toL[d][i]=toL[d][i-1]+1; } else if(val[d][i]>tmp) { val[d+1][rpos++]=val[d][i]; toL[d][i]=toL[d][i-1]; } else if(count>0) { val[d+1][lpos++]=val[d][i]; toL[d][i]=toL[d][i-1]+1; count--; } else { val[d+1][rpos++]=val[d][i]; toL[d][i]=toL[d][i-1]; } } build(lson,d+1); build(rson,d+1); } int query(int L,int R,int k,int l,int r,int rt,int d) { if(l==r) return val[d][L]; int s1; int s2; if(L!=l) { s1=toL[d][R]-toL[d][L-1]; s2=toL[d][L-1]-toL[d][l-1]; } else { s1=toL[d][R]-toL[d][L-1]; s2=0; } int new_L,new_R; int mid=(l+r)>>1; if(k<=s1) { new_L=l+s2; new_R=l+s1+s2-1; return query(new_L,new_R,k,lson,d+1); } else { k=k-s1; s1=(R-L+1)-s1; s2=L-l-s2; new_L=(mid+1)+s2; new_R=(mid+1)+s1+s2-1; return query(new_L,new_R,k,rson,d+1); } } int main(void) { // freopen("d:\\in.txt","r",stdin); int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); int i; for(i=1;i<=n;i++) { scanf("%d",&val[0][i]); sorted[i]=val[0][i]; } sort(sorted+1,sorted+1+n); build(1,n,1,0); int a,b,k; while(m--) { scanf("%d%d%d",&a,&b,&k); printf("%d\n",query(a,b,k,1,n,1,0)); } } return 0; }