K번째 수 (JUNGOL 7088)

https://jungol.co.kr/problem/7088

---

아이디어

구간 [L,R]에서 x이하의 수의 개수를 구하는것은 O(log N)에 가능합니다. 머지소트트리를 만들어주면 되기 때문입니다. 그러면 구간 [L,R]에서 K번째 수를 찾는것은 어떻게 할까요? 이분탐색을 통해 [L,R]에서 x이하의 수가 K이상인 최소의 x값을 찾아주면 됩니다. 그러면 하나의 쿼리를 O(log²N)으로 해결해줄 수 있습니다.

---

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

vector <ll> tree[2020202];

ll arr[505050]={0};
void init(ll s,ll e,ll node)
{
    if (s==e)
    {
        tree[node].push_back(arr[s]);
        return;
    }
    ll mid=(s+e)/2;
    init(s,mid,node*2);
    init(mid+1,e,node*2+1);

    ll idx1=0,idx2=0;
    while (idx1<tree[node*2].size() && idx2<tree[node*2+1].size())
    {
        if (tree[node*2][idx1]<tree[node*2+1][idx2]) tree[node].push_back(tree[node*2][idx1++]);
        else tree[node].push_back(tree[node*2+1][idx2++]);
    }
    while (idx1<tree[node*2].size()) tree[node].push_back(tree[node*2][idx1++]);
    while (idx2<tree[node*2+1].size()) tree[node].push_back(tree[node*2+1][idx2++]);
}
ll get(ll s,ll e,ll node,ll l,ll r,ll num) //num이하의 수의 개수 반환
{
    if (e<l || r<s) return 0;
    if (l<=s && e<=r) return upper_bound(tree[node].begin(),tree[node].end(),num)-tree[node].begin();
    ll mid=(s+e)/2;
    return get(s,mid,node*2,l,r,num)+get(mid+1,e,node*2+1,l,r,num);
}

ll solve(ll N,ll l,ll r,ll k)
{
    ll s=-1e9,e=1e9,Ans=1e9;
    while (s<=e)
    {
        ll mid=(s+e)/2;
        if (get(1,N,1,l,r,mid)>=k)
        {
            Ans=mid;
            e=mid-1;
        } 
        else s=mid+1;
    }
    return Ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,M,i,a,b,c;

    cin>>N>>M;
    for (i=1;i<=N;i++) cin>>arr[i];

    init(1,N,1);

    for (i=0;i<M;i++)
    {
        cin>>a>>b>>c;
        cout<<solve(N,a,b,c)<<"\n";
    }
}