Next Spaceship

Driving into future…

POJ 2104 K-th Number Report

| Comments

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:

POJ 2104 K-th Number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <cstring>
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)]);
    }
}

Comments