백준 2243 사탕상자

세그트리를 이용하여 해결하는 문제입니다.

 

사탕을 넣거나 빼면서 update를 하고 원하는 맛의 사탕을 찾을 때는 sum을 이용하여 해당 맛이 어딨는지 찾아야 합니다.

 

원하는 맛을 찾을 때는 지금 구간에서 왼쪽 / 오른쪽 자식 노드를 봤을때 왼쪽 노드에 내가 원하는 순위보다 높다면 왼쪽으로 이동 하고 그렇지 않다면 현재 알아야 하는 순위에서 왼쪽 노드의 값만큼을 빼고 오른쪽으로 진행해주면 됩니다.

 

아래는 코드입니다.

 

#include <iostream>

using namespace std;

#define MAX 1000000

int tree[MAX*4+10];
int arr[MAX+1];

void update(int node, int start, int end, int diff, int index) {

	if (index < start || index > end) return;

	tree[node] += diff;

	if (start != end) {
		update(node * 2, start, (start + end) / 2, diff, index);
		update(node * 2 + 1, (start + end) / 2 + 1, end, diff, index);
	}
}

int query(int node, int start, int end, int seq) {

	if (start == end) return start;
	

	if (tree[node * 2] >= seq) { //왼쪽 자식이 seq보다 크다면 왼쪽에 사탕이 있으므로 왼쪽으로 
		return query(node * 2, start, (start + end) / 2, seq);
	}
	else { //그렇지 않다면 오른쪽에 사탕이 있으므로 tree[node*2]만큼 빼준뒤 오른쪽으로
		return query(node * 2 + 1, (start + end) / 2+1, end, seq - tree[node * 2]);
	}
}


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

	for (int i = 0; i < n; i++) {
		int a, b, c; cin >> a;
		if (a == 2) {			
			cin >> b >> c;
			arr[b] += c;
			update(1, 1, MAX, c, b); //개수 업데이트
		}
		else { //쿼리 b번째 맛을 찾아야함
			cin >> b;
			int ans = query(1, 1, MAX, b); 
			cout << ans << '\n';
			arr[ans]--; 
			update(1, 1, MAX, -1, ans);	//1개 빼므로 -1 update
		}
	}
	return 0;
}