[백준/BOJ] 백준 1321번 : 군인

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

1321번: 군인

부대 인원에 대한 세그먼트 트리를 만들고 1번 부대부터 mid번 부대까지 인원이 몇 명인지 구하는 이분 탐색을 통해 문제를 해결했다.

 

코드

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

int n;
int m;
vector<int> people(500001, 0);
vector<int> sgmtt(500001 * 4, 0);

int MakeSgmtt(int here, int range_left, int range_right)
{
	if (range_left == range_right)
		return sgmtt[here] = people[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] = MakeSgmtt(left_child, range_left, range_mid) + MakeSgmtt(right_child, range_mid + 1, range_right);
}

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

	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] = UpdateSgmtt(left_child, range_left, range_mid, update_index) + UpdateSgmtt(right_child, range_mid + 1, range_right, update_index);
}

int QuerySgmtt(int here, int range_left, int range_right, int find_left, int find_right)
{
	if (find_right < range_left || range_right < find_left)
		return 0;

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

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

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

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

	cin >> n;

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

		people[i] = input;
	}

	MakeSgmtt(0, 1, n);

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int order, number, a;

		cin >> order;

		if (order == 1)
		{
			cin >> number >> a;

			people[number] += a;
			UpdateSgmtt(0, 1, n, number);
		}

		else
		{
			cin >> number;

			//number번 군인이 몇번 부대에 있는지 찾는다
			int left = 1;
			int right = n;
			int result = -1;

			while (left <= right)
			{
				int mid = (left + right) / 2;
				int people_num = QuerySgmtt(0, 1, n, 1, mid); //1번 부대부터 mid번 부대까지 인원이 몇명인지 구한다

				if (people_num >= number)
				{
					result = mid;

					right = mid - 1;
				}

				else
				{
					left = mid + 1;
				}
			}

			cout << result << "\n";
		}
	}

	return 0;
}