[ICPC] 백준 7469 - K번째 수

https://www.acmicpc.net/problem/7469

 

수열의 부분 구간에서 연산을 하는 것은 머지 소트 트리로 처리할 수 있다.

 

머지 소트 트리를 구현한 후 이진 탐색을 이용하여 구간의 k번째 원소를 찾아주면 된다.

 

전체 코드 - query 함수에서 lower_bound를 사용했으므로 kth - 1을 pivot으로 삼은 것에 유의하라.

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> mst[400000];
int ar[100001];

inline int mid(int s, int e) { return s + (e - s) / 2; }

void set_mst(int node, int start, int end)
{
    vector<int> &cur = mst[node];
    if (start == end)
    {
        cur.push_back(ar[start]);
        return;
    }

    int m = mid(start, end);
    set_mst(node * 2, start, m);
    set_mst(node * 2 + 1, m + 1, end);

    vector<int> &l = mst[node * 2], &r = mst[node * 2 + 1];

    cur.resize(l.size() + r.size());
    merge(l.begin(), l.end(), r.begin(), r.end(), cur.begin());
}

int query(int node, int start, int end, int l, int r, int x)
{
    if (l > end || r < start) return 0;
    if (l <= start && end <= r)
        return lower_bound(mst[node].begin(), mst[node].end(), x) - mst[node].begin();
    
    int m = mid(start, end);
    return query(node * 2, start, m, l, r, x) + query(node * 2 + 1, m + 1, end, l, r, x);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        cin >> ar[i];

    set_mst(1, 1, n);

    for (int j = 0; j < m; ++j)
    {
        int go, to, kth;
        cin >> go >> to >> kth;

        int l = -1e9, r = 1e9;
        int res;

        while (l <= r)
        {
            int m = mid(l, r);

            if (query(1, 1, n, go, to, m) <= kth - 1)
                res = m, l = m + 1;
            else
                r = m - 1;
        }

        cout << res << '\n';
    }
}