BOJ 2243 - 사탕 상자 (세그트리, k번째 수)

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

기본문제.

 

<문제 설명>

사탕의 맛이 1~1e6으로 주어질 때, 최대 1e5개의 쿼리가 주어진다.

 

1 : k  -> k번째로 맛있는 사탕의 맛 출력

2 : i d -> 맛i를 갖는 사탕의 수를 d만큼 변화

 

<풀이>

구간합 세그트리를 마련한다. 2번쿼리는 일반적인 세그트리 update와 같은 논리로 짜면 된다.

 

1번쿼리는 어떻게 짤까? 

 

예를 들어 3번째 원소를 찾으려고 할때, 왼쪽 자식노드에 3이하가 들어있다면 왼쪽자식노드로, 3초과가 들어있다면 우측자식노드로 재귀를 진행하면 된다.

// k번째 수 찾기
int kth(int node, int st, int en, const int k) {
	if (st == en) return st;	
	int mid = (st + en) / 2;
	if (k <= seg[node * 2])
		return kth(node * 2, st, mid, k);
	else
		return kth(node * 2 + 1, mid + 1, en, k - seg[node * 2]);	
}

 

<전체코드>

const int SMAX = (1<<21);
int seg[SMAX];
void update(int i, int x) {
	i += SMAX / 2;
	seg[i] = x;
	while (i > 1) {
		i /= 2;
		seg[i] = seg[i * 2] + seg[i * 2 + 1];
	}
}
int kth(int node, int st, int en, const int k) {
	if (st == en) return st;	
	int mid = (st + en) / 2;
	if (k <= seg[node * 2])
		return kth(node * 2, st, mid, k);
	else
		return kth(node * 2 + 1, mid + 1, en, k - seg[node * 2]);	
}

int main() {
	FAST;
	int tt; cin >> tt;
	while (tt--) {
		int cmd; cin >> cmd;
		if (cmd == 2) {
			int box, diff; cin >> box >> diff;
			update(box, seg[SMAX / 2 + box] + diff);
		}
		else {
			int k; cin >> k;
			int box = kth(1, 1, SMAX / 2 - 1, k);
			cout << box << '\n';
			update(box, seg[SMAX / 2 + box] - 1);
		}
	}
}

 

<생각>

1e6을 넘어서는 값에 대해선 좌표압축이 필요해 보인다