C++[백준]2243번 사탕상자

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

2243번: 사탕상자

 

솔루션

---

처음에 특정 사탕을 꺼낼 방법을 고민을 했다.

 

그런데, 개수를 저장하는 세그먼트 트리를 구성하면, 

1부터 특정 맛 까지 총 몇개가 있는지 알 수 있다.

이 점을 이용해서 세그먼트 트리를 만들고, 세그먼트 트리를 갱신한다면 풀 수 있을 것이라 생각했다.

 

1) A가 1일 때, 사탕 상자에서 사탕을 빼내는 경우이기 때문에, 왼쪽노드는 더 맛있는 사탕이 있는 총 개수이다.

왼쪽 노드의 개수가 골라야 하는 개수보다 작거나 같을 때 왼쪽으로 가고, 왼쪽노드의 개수보다 큰 경우는 오른쪽으로 가되, 왼쪽 노드의 개수만큼 빼 준다.

그리고 각 노드에서는 사탕을 빼기 때문에 1을 빼준다.

 

2) 사탕상자에 C만큼 더해준다. 

 

 

 

코드

---

#define MAX 1000000
#include <iostream>
using namespace std;

int seg[4000002];
int N;

void updateSeg(int str, int end, int node, int idx, int val) {
	seg[node] += val;
	if (str == end) return;
	else {
		int mid = (str + end) / 2;
		if (idx <= mid) return updateSeg(str, mid, node * 2, idx, val);
		else return updateSeg(mid + 1, end, node * 2 + 1, idx, val);
	}
}

int getSeg(int str, int end, int node,int cnt) {
	seg[node]--;
	if (str == end) {
		return str;
	}
	else {
		int mid = (str + end) / 2;
		if (seg[node * 2] >= cnt) {
			return getSeg(str, mid, node * 2, cnt);
		}
		else {
			return getSeg(mid + 1, end, node * 2 + 1, cnt - seg[node * 2]);
		}
	}
}

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

	cin >> N;
	while (N--) {
		int A, B, C;
		cin >> A >> B;

		//구간 합 배열?로  해결 가능?
		if (A == 1) { //사탕상자에서 사탕을 꺼내는 경우
			cout << getSeg(1, MAX, 1, B) << "\n";
		}
		else {//사탕 상자에 사탕을 넣거나 빼는 경우
			cin >> C;
			updateSeg(1, MAX, 1, B, C);
		}
	}
}