[백준/BOJ] 백준 7469번 : K번째 수

[백준/BOJ] 백준 7469번 : K번째 수

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

노드에 해당 구간에 정렬된 값들이 저장되는 머지 소트 트리를 만들고 특정 구간에서 어떤 숫자 이하의 개수가 몇 개인지 구하는 쿼리를 만들어 이분 탐색을 통해 문제를 해결했다.

코드

#include #include #include using namespace std; int n, m; vector inputs(100001, 0); vector mgstt[400004]; //머지소트트리 vector::iterator it; //머지소트트리를 이용해 문제를 해결했다 (세그먼트트리와 유사하지만 노드에 해당 구간에 정렬된 값이 저장) vector MergeMgstt(vector& left, vector& right) { vector ret; int left_i = 0; int right_i = 0; while (left_i < left.size() && right_i < right.size()) { if (left[left_i] <= right[right_i]) { ret.push_back(left[left_i]); left_i++; } else { ret.push_back(right[right_i]); right_i++; } } while (left_i < left.size()) { ret.push_back(left[left_i]); left_i++; } while (right_i < right.size()) { ret.push_back(right[right_i]); right_i++; } return ret; } vector MakeMgstt(int here, int range_left, int range_right) { if (range_left == range_right) { mgstt[here].push_back(inputs[range_left]); return mgstt[here]; } int left_child = here * 2 + 1; int right_child = here * 2 + 2; int range_mid = (range_left + range_right) / 2; vector left = MakeMgstt(left_child, range_left, range_mid); vector right = MakeMgstt(right_child, range_mid + 1, range_right); mgstt[here] = MergeMgstt(left, right); return mgstt[here]; } //find_left~find_right 구간에서 check이하의 개수를 리턴 int QueryMgstt(int here, int range_left, int range_right, int find_left, int find_right, int check) { if (find_right < range_left || range_right < find_left) return 0; if (find_left <= range_left && range_right <= find_right) { it = lower_bound(mgstt[here].begin(), mgstt[here].end(), check); if (it == mgstt[here].end() || (*it) != check) return it - mgstt[here].begin(); else return it - mgstt[here].begin() + 1; } int left_child = here * 2 + 1; int right_child = here * 2 + 2; int range_mid = (range_left + range_right) / 2; return QueryMgstt(left_child, range_left, range_mid, find_left, find_right, check) + QueryMgstt(right_child, range_mid + 1, range_right, find_left, find_right, check); } int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; i++) { int input; cin >> input; inputs[i] = input; } MakeMgstt(0, 1, n); for (int i = 0; i < m; i++) { int a, b, k; cin >> a >> b >> k; int left = -1000000000; int right = 1000000000; int result = -1; while (left <= right) { int mid = (left + right) / 2; //a~b구간에서 mid이하의 수의 개수를 리턴 int query_ret = QueryMgstt(0, 1, n, a, b, mid); if (query_ret >= k) { result = mid; right = mid - 1; } else { left = mid + 1; } } cout << result << "

"; } return 0; }

from http://geniusjo-story.tistory.com/528 by ccl(A) rewrite - 2021-09-04 04:00:34