算法训练 区间k大数查询 时间限制：1.0s 内存限制：256.0MB
问题描述 给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。
输入格式 第一行包含一个数n，表示序列长度。
第二行包含n个正整数，表示给定的序列。
第三个包含一个正整数m，表示询问个数。
接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。
输出格式 总共输出m行，每行一个数，表示询问的答案。 样例输入 5 1 2 3 4 5 2 1 5 2 2 3 2 样例输出 4 2 数据规模与约定 对于30%的数据，n,m<=100；
对于100%的数据，n,m<=1000；
保证k<=(r-l+1)，序列中的数<=106。
#include<iostream> #include<stdio.h> #include<algorithm> #include<vector> using namespace std; struct Node { int l; int r; int sum; Node() { sum = 0; } }T[100007 * 40]; int cnt =0; int n,m; int root[100007],a[100007]; vector<int> v; int getid(int x) { return lower_bound(v.begin(),v.end(),x) - v.begin() + 1; } void update(int l,int r,int &x,int y,int pos) { T[++cnt] = T[y]; T[cnt].sum ++; x = cnt; if(l==r) return; int mid = (l + r)/2; if(pos <= mid) update(l,mid,T[x].l,T[y].l,pos); else update(mid + 1,r,T[x].r,T[y].r,pos); } int query(int l,int r,int x,int y,int k) { if(l == r) return l; int mid = (l + r)/2; int sum = T[T[y].l].sum - T[T[x].l].sum; if(sum >= k) return query(l,mid,T[x].l,T[y].l,k); else return query(mid+1,r,T[x].r,T[y].r,k - sum); } int main() { scanf("%d",&n); for(int i =1;i<=n;i++) { scanf("%d",&a[i]); v.push_back(a[i]); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i =1;i<= n;i++) { update(1,n,root[i],root[i-1],getid(a[i])); } scanf("%d",&m); while(m--) { int x,y,k; scanf("%d%d%d",&x,&y,&k); if(x>y) swap(x,y); k = (y - x + 1) - k + 1; printf("%d\n",v[query(1,n,root[x-1],root[y],k) - 1]); } return 0; }