Kth number

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cctype> 5 #include<cmath> 6 #include<cstring> 7 #include<map> 8 #include<stack> 9 #include<set>10 #include<vector>11 #include<algorithm>12 #include<string.h>13 #define ll long long14 #define LL unsigned long long15 using namespace std;16 const int INF=0x3f3f3f3f;17 const double eps=0.0000000001;18 const int N=100000+10;19 struct node{20     int left,right;21     int val;22 }tree[N*40];23 int cnt;24 int a[N],b[N];25 int root[N];26 int build(int l,int r){27     int pos=++cnt;28     tree[pos].val=0;29     if(l==r)return pos;30     int mid=(l+r)>>1;31     tree[pos].left=build(l,mid);32     tree[pos].right=build(mid+1,r);33     return pos;34 }35 void update(int pre,int &now,int x,int l,int r){36     tree[++cnt]=tree[pre];37     now=cnt;38     tree[now].val++;39     if(l==r)return;40     int mid=(l+r)>>1;41     if(x<=mid){42         update(tree[pre].left,tree[now].left,x,l,mid);43     }44     else{45         update(tree[pre].right,tree[now].right,x,mid+1,r);46     }47 48 }49 int query(int L,int R,int k,int l,int r){50     if(l==r) return l;51     int mid=(l+r)>>1;52     int sum=tree[tree[R].left].val-tree[tree[L].left].val;53     if(k<=sum){54         return query(tree[L].left,tree[R].left,k,l,mid);55     }56     else{57         return query(tree[L].right,tree[R].right,k-sum,mid+1,r);58     }59 60 }61 int main()62 {63     int t;64     scanf("%d",&t);65     while(t--){66         memset(root,0,sizeof(root));67         memset(a,0,sizeof(a));68         memset(b,0,sizeof(b));69         int n,m;70         scanf("%d%d",&n,&m);71         cnt=0;72         for(int i=1;i<=n;i++) {73             scanf("%d",&a[i]);74             b[i]=a[i];75         }76         sort(b+1,b+1+n);77         int tt = unique(b+1,b+1+n)-b-1;78         for(int i=1;i<=n;i++) {79             a[i]=lower_bound(b+1,b+1+tt,a[i])-b;//二分找到a[i]的位置81             update(root[i-1],root[i],a[i],1,tt);//root[i-1]表示上一个版本的线段树82         }83         for(int i=1;i<=m;i++) {84             int l,r,k;85             scanf("%d%d%d",&l,&r,&k);86             int ans=query(root[l-1],root[r],k,1,tt); //ans是第k个数的位置87             printf("%d\n", b[ans]);//因为询问的是哪个数,所以要b[ans]88         }89     }90     return 0;91 }