[백준/BOJ] 백준 1572번 : 중앙값

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

1572번: 중앙값

[해당 숫자] = 나온 횟수를 통해 해당 숫자가 나온 횟수를 저장하고 이것을 합 세그먼트 트리로 만들어서 이분 탐색을 통해 중앙값을 찾는 방법으로 문제를 해결했다.

 

코드

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

int n;
int k;
long long result = 0;
vector<int> temp;
vector<int> number_cnt(65537, 0); //[해당숫자] = 나온횟수
deque<int> dq;

vector<int> sgmtt(65537 * 4, 0); //합 세그먼트 트리

int Make_sgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
	{
		return sgmtt[here] = number_cnt[range_left];
	}

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return sgmtt[here] = Make_sgmtt(left_child, range_left, range_mid) + Make_sgmtt(right_child, range_mid + 1, range_right);
}

int Query_sgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_left <= range_left && range_right <= find_right)
		return sgmtt[here];

	if (find_right < range_left || range_right < find_left)
		return 0;

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return Query_sgmtt(left_child, range_left, range_mid, find_left, find_right) + Query_sgmtt(right_child, range_mid + 1, range_right, find_left, find_right);
}

int Update_sgmtt(int here, int range_left, int range_right, int update_index)
{
	if (range_left == range_right && range_right == update_index)
		return sgmtt[here] = number_cnt[range_left];

	if (update_index < range_left || range_right < update_index)
		return sgmtt[here];

	int left_child = here * 2 + 1;
	int right_child = here * 2 + 2;
	int range_mid = (range_left + range_right) / 2;

	return sgmtt[here] = Update_sgmtt(left_child, range_left, range_mid, update_index) + Update_sgmtt(right_child, range_mid + 1, range_right, update_index);
}

int Solve()
{
	int left = 0;
	int right = 65536; //나올수 있는 온도의 최댓값
	int result = -1;

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

		//mid온도 이하의 개수가 ((k + 1) / 2)개 이상일때
		if (Query_sgmtt(0, 0, 65536, 0, mid) >= ((k + 1) / 2))
		{
			result = mid;

			right = mid - 1;
		}

		else
		{
			left = mid + 1;
		}
	}

	return result;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	cin >> k;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		temp.push_back(input);
	}

	int range_k_left = 0;
	int range_k_right = k - 1;
	for (int i = 0; i < k; i++)
	{
		dq.push_back(temp[i]);
		number_cnt[temp[i]]++;
	}

	Make_sgmtt(0, 0, 65536);
	result += (long long)Solve();

	while (1)
	{
		//더이상의 k구간이 없을때
		if (range_k_right == n - 1)
			break;

		number_cnt[dq.front()]--;
		Update_sgmtt(0, 0, 65536, dq.front());
		dq.pop_front();
		range_k_left++;

		range_k_right++;
		dq.push_back(temp[range_k_right]);
		number_cnt[dq.back()]++;
		Update_sgmtt(0, 0, 65536, dq.back());

		result += (long long)Solve();
	}

	cout << result;

	return 0;
}