[BOJ 7469] K번째 수

[BOJ 7469] K번째 수 - P3

 

문제 설명 : 

 

문제 풀이 : 

mergesort tree를 이용해서 풀 수 있다. megesort tree는 트리의 노드가 값 하나가 아니라, 원소 그 자체를 담고 있기 때문에 여러개의 원소를 담고 있을 수 있다. 마치 merge sort가 되는 과정을 tree화 시킨 것이라고 보면 된다.

그래서 이분탐색으로 mid값을 지정하여 [l,r]구간에 mid 이하의 값이 몇 개인지를 log 만에 찾을 수 있다.

 

배울 점 : 

mergesort Tree를 이용하면 N개의 원소 중에서 [l,r]구간의 x보다 크거나 작은 원소의 개수를 log만에 구할 수 있다.

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

const int SIZE = 100009;
vector<int> tree[SIZE*8];
int startIdx=1;

void makeMergeSortTree(){
    for(int i = startIdx - 1; i>=1 ; i--){
        int lChild = i*2,rChild = i*2+1;
        int lIdx = 0,rIdx = 0;
        int sz = tree[lChild].size();

        while(lIdx < sz && rIdx < sz){
            if(tree[lChild][lIdx] > tree[rChild][rIdx]) tree[i].push_back(tree[rChild][rIdx++]);
            else tree[i].push_back(tree[lChild][lIdx++]);
        }

        if(lIdx < sz){
            for(int j = lIdx ; j < sz ; j++){
                tree[i].push_back(tree[lChild][j]);
            }
        }
        else for(int j = rIdx ; j < sz ; j++){
            tree[i].push_back(tree[rChild][j]);
        }
    }

}

int query(int node,int cl, int cr,int ql,int qr,int x){
    if(cl > qr || ql > cr) return 0;
    if(qr >= cr && cl >= ql) {
        int cnt = upper_bound(tree[node].begin(), tree[node].end(), x) - tree[node].begin() ;
        return cnt;
    }

    int mid = (cl+cr)/2;
    return query(node*2,cl,mid,ql,qr,x) + query(node*2+1,mid+1,cr,ql,qr,x);
}

int main(){
    int n,q;    scanf("%d %d",&n,&q);

    for(; startIdx < n ; startIdx *= 2);
    for(int i=1 ; i<=n ; i++){
        int inp;    scanf("%d",&inp);
        tree[startIdx + i - 1].push_back(inp);
    }

    for(int i=startIdx+n ; i <= startIdx*2 ; i++){
        tree[i].push_back(2e9);
    }

    makeMergeSortTree();

    while(q--){
        int ql,qr,x;  scanf("%d %d %d",&ql,&qr,&x);

        int l = -1e9-3,r = 1e9+3;
        while(l+1 < r){
            int mid = (l+r)/2;
            if(query(1,1,startIdx,ql,qr,mid) >= x) r = mid;
            else l = mid;
        }

        printf("%d\n",r);
    }
    return 0;
}