K-th Number POJ - 2104(归并树)
题解:使用归并树
把数列用线段树维护起来,线段树的每个节点都保存了对应区间排好序的结果。
建立线段树的过程和归并排序类似,而每个节点的数列就是其两个儿子节点的数列合并后的结果。
建树的复杂度是O(nlogn)。这颗线段树正是归并排序的完整再现。
要计算再某个区间中不超过x的数的个数,只需要递归地进行如下操作:
如果所给的区间和当前区间完全没有交集,那么返回0个
如果所给的区间完全包含了当前节点对应的区间,那么使用二分搜索法对该节点上保存的数组进行查找。
否则对两个儿子进行递归地进行计算之后求和即可
由于对于同一深度的节点最多只访问常数个,因此可以在O(log^2(n))时间里求出不超过x的数的个数。所以整个算法的复杂度是O(nlogn+mlog^3(n)).
附上代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=1e5+50;
const int MAX_M=5e3+50;
const int ST_SIZE=(MAX_N)<<2;
int N,M;
int A[MAX_N];
int I[MAX_M],J[MAX_M],K[MAX_N];
int nums[MAX_N];
vector<int>dat[ST_SIZE];
void init(int k,int l,int r)
{
if(r-l==1){
dat[k].push_back(A[l]);
}else{
int lch=k*2+1,rch=k*2+2;
init(lch,l,(l+r)/2);
init(rch,(l+r)/2,r);
dat[k].resize(r-l);
merge(dat[lch].begin(),dat[lch].end(),dat[rch].begin(),dat[rch].end(),dat[k].begin());
}
}
int query(int i,int j,int x,int k,int l,int r)
{
if(j<=l||r<=i){
return 0;
}else if(i<=l&&r<=j){
return upper_bound(dat[k].begin(),dat[k].end(),x)-dat[k].begin();
}else{
int lc=query(i,j,x,k*2+1,l,(l+r)/2);
int rc=query(i,j,x,k*2+2,(l+r)/2,r);
return lc+rc;
}
}
void solve()
{
for(int i=0;i<N;i++){
nums[i]=A[i];
}
sort(nums,nums+N);
init(0,0,N);
for(int i=0;i<M;i++){
int l=I[i]-1,r=J[i],k=K[i];
int lb=-1,ub=N;
while(ub-lb>1){
int md=(ub+lb)/2;
int c=query(l,r,nums[md],0,0,N);
if(c>=k){
ub=md;
}else{
lb=md;
}
}
printf("%d\n",nums[ub]);
}
}
int main()
{
scanf("%d%d",&N,&M);
for(int i=0;i<N;i++){
scanf("%d",&A[i]);
}
for(int i=0;i<M;i++){
scanf("%d%d%d",&I[i],&J[i],&K[i]);
}
solve();
return 0;
}