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

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

7469번: K번째 수

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

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
vector<int> inputs(100001, 0);
vector<int> mgstt[400004]; //머지소트트리
vector<int>::iterator it;

//머지소트트리를 이용해 문제를 해결했다 (세그먼트트리와 유사하지만 노드에 해당 구간에 정렬된 값이 저장)

vector<int> MergeMgstt(vector<int>& left, vector<int>& right)
{
	vector<int> 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<int> 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<int> left = MakeMgstt(left_child, range_left, range_mid);
	vector<int> 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 << "\n";
	}

	return 0;
}