线段树之区间k大查询 二分查值 思路源自《算法竞赛入门经典训练指南》

一、思路来源

《算法竞赛入门经典训练指南》P306页上，有一种解决思路：设数x属于区间[-Inf,Inf]，假定x是待查询区间上的第k大，那么该区间上大于x的数一定有k-1个。如果该区间上大于x的数小于k-1个，说明x过大，反之过小。 只要在[-Inf,Inf]上不断二分的查询x，肯定能找到第k大。

详细思路见书。

二、代码

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX_N (int)(1e7+1)
#define Inf 1e6+1
#define l(x) (x<<1)
#define r(x) (x<<1|1)
vector<int> dat[MAX_N];
int N;
void build(int i,int l,int r){
	if(l==r){//叶子节点 
		dat[i].push_back(-1);
		int a;
		cin>>a;
		dat[i].push_back(a);
		return;
	}
	int mid=(l+r)>>1;
	build(l(i),l,mid);//递归构建左子数 
	build(r(i),mid+1,r);//递归构建右子树
 
	//归并排序：多个有序的小区间和并成一个有序的大区间 
	int ll=l(i),rr=r(i),llen=dat[ll].size()-1,rlen=dat[rr].size()-1;
	int x=1,y=1;
	dat[i].push_back(-1);//下标0位置上填充一个数-1，是为了后边二分查找方便 
	while(x<=llen&&y<=rlen){
		if(dat[ll][x]>dat[rr][y]) dat[i].push_back(dat[rr][y++]);
		else dat[i].push_back(dat[ll][x++]);
	}
	while(x<=llen) dat[i].push_back(dat[ll][x++]);
	while(y<=rlen) dat[i].push_back(dat[rr][y++]);	
}

int node_search(int i,int x){//查询结点i所维护的序列中大于等于x的数有多少个
	return dat[i].end()-upper_bound(dat[i].begin()+1,dat[i].end(),x);
}

/*
    Q:查询区间[s,t]上大于x的数的个数
    [s,t]:待查询区间
    i:当前查询结点在线段树中的位置
    [l,r]:当前查询区间
    return：结果
    调用时：int res=Q(s,t,1,1,N,x);//第3个参数是线段树中的第1个结点，[1,N]是其表示区间

*/
int Q(int s,int t,int i,int l,int r,int x){
	//两个区间无交集 
	if(r<s||l>t) return 0;
	// [s,t]完全包含[l,r] 
	if(s<=l&&r<=t){
		return node_search(i,x);
	}
	else{
		int mid=(l+r)>>1;
		int t1=Q(s,t,l(i),l,mid,x);
		int t2=Q(s,t,r(i),mid+1,r,x);
		return t1+t2;
	}
}
/*
	二分查找区间第k大x 
*/
int search(int s,int t,int k){
	int l=-Inf,r=Inf,res,mid,cnt;
	while(l<=r){
		mid=(l+r)>>1;
		cnt=Q(s,t,1,1,N,mid);//查询区间[s,t]上大于等于mid的数的个数 ；如果有k-1个数大于等于mid说明mid是第k大
		if(cnt>=k) //mid过于小，则增大
			l=mid+1;
		else//mid过于大，则减小
			r=mid-1;
	}
	return l;
}
	
int main(){
	cin>>N;
	build(1,1,N);
	int m,s,t,k;
	cin>>m;
	while(m--){
		cin>>s>>t>>k;
		cout<<search(s,t,k)<<endl;
	}
	return 0;
}