第k大的数
描述 你为Macrohard公司的数据结构部门工作，你的工作是重新写一个数据结构，这个数据结构能快速地找到一段数列中第k大的数。
就是说，给定一个整数数列a[1…n]，其中每个元素都不相同，你的程序要能回答一组格式为Q (i , j , k)的查询，Q(i, j ,k)的意思是“在a[i…j]中第k大的数是多少？”
例如令 a = {1, 5, 2, 6, 3, 7, 4}，查询格式为Q (2 , 5 , 3)，数列段a[2…5] = {5, 2, 6, 3}，第3大的数是5，所以答案是5。
输入 文件第一行包括一个正整数n，代表数列的总长度，还有一个数m，代表有m个查询。 n，m满足：1≤n≤100 000, 1≤m≤5 000 第二行有n个数，代表数列的元素，所有数都不相同，而且不会超过109 接下来有m行，每行三个整数i , j , k，代表一次查询， i , j , k满足1≤i≤j≤n, 1≤k≤j − i + 1
输出 输出每个查询的答案，用换行符隔开
样例输入 [复制] 7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3 样例输出 [复制] 5 6 3
#include<bits/stdc++.h> using namespace std; inline int read() { int data=0;int w=1; char ch=0; ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar(); return data*w; } const int N=1e5+10; int L[N<<5],R[N<<5],T[N],sum[N<<5]; int n,m,tot=0; int a[N],w[N]; inline int build(int l,int r){ int rt=++tot;sum[rt]=0; if(l<r){ int mid=(l+r)>>1; L[rt]=build(l,mid); R[rt]=build(mid+1,r); } return rt; } inline int update(int pre,int l,int r,int x){ int rt=++tot; L[rt]=L[pre],R[rt]=R[pre],sum[rt]=sum[pre]+1; if(l<r){ int mid=(l+r)>>1; if(x<=mid){ L[rt]=update(L[pre],l,mid,x); } else{ R[rt]=update(R[pre],mid+1,r,x); } } return rt; } inline int que(int prel,int prer,int l,int r,int k){ if(l>=r) return l; int mid=(l+r)>>1; int num=sum[L[prer]]-sum[L[prel]]; if(num>=k) return que(L[prel],L[prer],l,mid,k); else return que(R[prel],R[prer],mid+1,r,k-num); } int main(){ n=read();m=read(); for(int i=1;i<=n;i++){ a[i]=read();w[i]=a[i]; } sort(w+1,w+n+1); int s1=unique(w+1,w+n+1)-w-1; T[0]=build(1,s1); for(int i=1;i<=n;i++){ int x=lower_bound(w+1,w+s1+1,a[i])-w; T[i]=update(T[i-1],1,s1,x); } while(m--){ int l=read(),r=read(),k=read(); int x=que(T[l-1],T[r],1,s1,k); printf("%d\n",w[x]); } return 0; }