백준 7469 K번째 수 (c++) : 피너클

7469번: K번째 수

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

 

머지소트 트리를 만들고 이분 탐색을 이용해서 풀었다.

 

int n, m;
int arr[100001];

vector<int> segtree[4 * 100001];

입력받을 배열과 머지소트 트리를 위한 segtree를 만들어준다.

void init(int node, int start, int end, int left, int right) {
	if (end < left || right < start) return;
	if (start == end) {
		segtree[node].push_back(arr[start]);
		return;
	}

	int mid = (start + end) / 2;
	init(node * 2, start, mid, left, right);
	init(node * 2 + 1, mid + 1, end, left, right);
	
	int left_length = segtree[node * 2].size();
	int right_length = segtree[node * 2 + 1].size();

	int left_now = 0, right_now = 0;

	while (left_now < left_length && right_now < right_length) {
		if (segtree[node * 2][left_now] < segtree[node * 2 + 1][right_now]) {
			segtree[node].push_back(segtree[node * 2][left_now]);
			left_now++;
		}
		else {
			segtree[node].push_back(segtree[node * 2 + 1][right_now]);
			right_now++;
		}
	}
	while (left_now < left_length) {
		segtree[node].push_back(segtree[node * 2][left_now]);
		left_now++;
	}
	while (right_now < right_length) {
		segtree[node].push_back(segtree[node * 2 + 1][right_now]);
		right_now++;
	}
}

머지소트트리 init함수이다. 자신의 자식 트리에서 받아온 것들을 크기에 맞춰서 자기 자신에게 넣어주면 된다.

 

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

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

	init(1, 1, n, 1, n);

입력을 받고 init해준다.

 

	while (m-- > 0) {
		int i, j, k;
		cin >> i >> j >> k;

		int left = -100000000, right = 100000000;

그 후 이분탐색을 할것이다. left와 right는 1e9로 해준다. 주어지는 숫자의 최대 범위이다.

 

		while (left <= right) {
			int mid = (left + right) / 2;

			int v = query(1, 1, n, i, j, mid);

			if (v < k) left = mid + 1;
			else if(v >= k) right = mid - 1;
		}

		cout << left << '\n';
	}

그 후 이분탐색을 돌리며 숫자를 맞춰가면 된다.

query는 i와 j 사이의 값들 중 mid보다 작거나 같은 값의 수를 보낸다.

i와 j사이의 값들중 mid보다 작은 값 v가 우리가 찾고자 하는 k보다 작다면 left를 높여주고

아니면 right를 내린다.

그후 left를 출력하면 된다.

int query(int node, int start, int end, int left, int right, int val) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) {
		auto it = upper_bound(segtree[node].begin(), segtree[node].end(), val);
		return it - segtree[node].begin();
	}

	int mid = (start + end) / 2;
	return query(node * 2, start, mid, left, right, val) + query(node * 2 + 1, mid + 1, end, left, right, val);
}

query함수다.

upper_bound를 이용해서 수를 찾아준다.

 

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

using namespace std;

int n, m;
int arr[100001];

vector<int> segtree[4 * 100001];

void init(int node, int start, int end, int left, int right) {
	if (end < left || right < start) return;
	if (start == end) {
		segtree[node].push_back(arr[start]);
		return;
	}

	int mid = (start + end) / 2;
	init(node * 2, start, mid, left, right);
	init(node * 2 + 1, mid + 1, end, left, right);
	
	int left_length = segtree[node * 2].size();
	int right_length = segtree[node * 2 + 1].size();

	int left_now = 0, right_now = 0;

	while (left_now < left_length && right_now < right_length) {
		if (segtree[node * 2][left_now] < segtree[node * 2 + 1][right_now]) {
			segtree[node].push_back(segtree[node * 2][left_now]);
			left_now++;
		}
		else {
			segtree[node].push_back(segtree[node * 2 + 1][right_now]);
			right_now++;
		}
	}
	while (left_now < left_length) {
		segtree[node].push_back(segtree[node * 2][left_now]);
		left_now++;
	}
	while (right_now < right_length) {
		segtree[node].push_back(segtree[node * 2 + 1][right_now]);
		right_now++;
	}
}

int query(int node, int start, int end, int left, int right, int val) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) {
		auto it = upper_bound(segtree[node].begin(), segtree[node].end(), val);
		return it - segtree[node].begin();
	}

	int mid = (start + end) / 2;
	return query(node * 2, start, mid, left, right, val) + query(node * 2 + 1, mid + 1, end, left, right, val);
}

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

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

	init(1, 1, n, 1, n);

	while (m-- > 0) {
		int i, j, k;
		cin >> i >> j >> k;

		int left = -100000000, right = 100000000;

		while (left <= right) {
			int mid = (left + right) / 2;

			int v = query(1, 1, n, i, j, mid);

			if (v < k) left = mid + 1;
			else if(v >= k) right = mid - 1;
		}

		cout << left << '\n';
	}

	return 0;
}

전체코드다.