K-th
Time |
|
Memory |
Total |
|
Accepted:8434 |
Description
You
That
For
Input
The
The
The
Output
For
Sample
7
1
2
4
1
Sample
5
6
3
Hint
This
标准的划分树:
#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); while(scanf("%d%d",&n,&m)==2) { 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; }