View the problem description here: 2104 K-th Number .
To solve this problem, you need to learn the following knowledge first.
- Segment Tree
- Binary Search
- Merge Sort
If you know all the above, it’s easy to solve this problem.
Try to solve by yourself, and don’t look my source code:
``` cpp POJ 2104 K-th Number
#include
#include
#include
#include
#include
using namespace std;
#define maxn 100010
#define maxm 20
int n,m;
int a[maxn];
int sorted[maxm][maxn];
struct node{
int l,r,d;
node* lc,*rc;
};
node mem[maxm*maxn];
int pos;
node *root;
int b,e,k;
node* maketree(int l,int r,int d){
if(l>r)return 0;
node* n1=&mem[pos++];
n1->l=l,n1->r=r,n1->d=d;
if(l==r){
sorted[d][l]=a[l];
return n1;
}
int mid=(l+r)/2;
n1->lc=maketree(l,mid,d+1);
n1->rc=maketree(mid+1,r,d+1);
int i,j,k;
i=l,j=mid+1,k=l;
while(i<=mid&&j<=r){
if(sorted[d+1][i]<sorted[d+1][j])
sorted[d][k++]=sorted[d+1][i++];
else
sorted[d][k++]=sorted[d+1][j++];
}
while(i<=mid)sorted[d][k++]=sorted[d+1][i++];
while(j<=r)sorted[d][k++]=sorted[d+1][j++];
return n1;
}
int search2(int l,int r,int d,int u){
if(l==r+1)return l;
int mid=(l+r)/2;
if(u<=sorted[d][mid])return search2(l,mid-1,d,u);
else return search2(mid+1,r,d,u);
}
int query(int u,node *n1){
if(b<=n1->l&&n1->r<=e){
return search2(n1->l,n1->r,n1->d,u)-n1->l;
}
else{
int ret=0;
int mid=(n1->l+n1->r)/2;
if(b<=mid)ret+=query(u,n1->lc);
if(e>=mid+1)ret+=query(u,n1->rc);
return ret;
}
}
int search1(int l,int r){
if(l==r+1){
return r;
}
int mid=(l+r)/2;
//cout<<"l="<<l<<",r="<<r<<endl;
//cout<<"mid="<<mid<<endl;
int x=query(sorted[1][mid],root);
//cout<<"x="<<x<<endl;
//cout<<"k="<<k<<endl;
if(x<=k)return search1(mid+1,r);
else return search1(l,mid-1);
}
int main(){
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;i++)scanf("%d",&a[i]);
pos=0;
root=maketree(1,n,1);
/*for(i=1;i<=10;i++){
for(j=1;j<=7;j++)
printf("%d ",sorted[i][j]);
cout<<endl;
}*/
for(i=1;i<=m;i++){
scanf("%d%d%d",&b,&e,&k);
k--;
printf("%d\n",sorted[1][search1(1,n)]);
}
}
```