백준 #7469 K번째 수


BOJ #7469 - K번째 수

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

# 문제 분류

세그먼트 트리 (Merge Sort Tree) + 이분 탐색

풀이 접근 방법


  1. 세그먼트 트리를 머지 소트 하듯이 관리해줍니다. 즉, 각각의 노드가 벡터로 이루어지게끔 합니다.
  2. 구간 내의 k번째 수는 특별한 성질이 있습니다. 바로 자기 자신보다 작은 수가 k 미만 개 존재한다는 것입니다.
  3. 세그먼트 트리로 바로 이 수를 찾을 수 없고, 가능한 범위 안에서 이분 탐색을 이용해 적절히 대입해보며 찾아야 합니다.

세그트리는 어느정도 익숙해졌다 생각했는데... ㅠ

개인적으로는 굉장히 어렵게 느껴지는 문제인 것 같습니다.


#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int N, M;
int i, j, k, p;
const int stMAX = 1 << 18;
vector<int> tree[stMAX];

struct SegTree {
    int start = stMAX / 2;

    void update(int l, int r, int value) {
        update(l, r, 1, 0, start - 1, value);
    }
    void update(int l, int r, int node, int ns, int ne, int value) {
        if (r < ns || ne < l) {
            return;
        }
        tree[node].push_back(value);
        if (node < start) {
            int mid = ns + ne >> 1;
            update(l, r, node * 2, ns, mid, value);
            update(l, r, node * 2 + 1, mid + 1, ne, value);
        }
    }

    int find(int s, int e, int value) {
        return find(s, e, 1, 0, start - 1, value);
    }
    int find(int s, int e, int node, int ns, int ne, int value) {
        if (e < ns || ne < s) {
            return 0;
        }
        if (s <= ns && ne <= e) {
            return upper_bound(tree[node].begin(), tree[node].end(), value) - tree[node].begin();
        }
        int mid = ns + ne >> 1;
        return find(s, e, node * 2, ns, mid, value) + find(s, e, node * 2 + 1, mid + 1, ne, value);
    }
} st;

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> p;
        st.update(i, i, p);
    }

    for (int i = 0; i < stMAX; i++) {
        sort(tree[i].begin(), tree[i].end());
    }

    for (int a = 0; a < M; a++) {
        cin >> i >> j >> k;

        int r = 1e9;
        int l = -r;
        int mid = l + r >> 1;

        while (l <= r) {
            mid = l + r >> 1;
            if (st.find(i - 1, j - 1, mid) < k)
                l = mid + 1;
            else
                r = mid - 1;
        }

        cout << l << "\n";
    }
}