백준 12899 / C++

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

12899번: 데이터 구조

 

[ 풀이 ] 

값을 인덱스로, 그 값의 개수를 저장하는 세그트리를 만들어주자.

(값을 인덱스로 세팅하는 방식은 자주 사용되는 방법이니 알아둡시다.) 

중복에 주의하자. 이미 있는 수도 추가해줘야 X번째로 작은 수를 찾을 수 있다. 

저장된 곳에서 X번째로 작은수는 값이 인덱스로 세팅된 세그트리에서 X번째 수를 찾으면 된다. 

 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
const int MAX = 2000002;
int n, m, T, x, tree[4 * MAX];

// sum tree update 
void upd(int node, int s, int e, int idx, int v) {
	if (idx<s || idx>e) return;
	if (s == e) {
		tree[node] += v;
		return;
	}
	int m = (s + e) / 2;
	upd(2 * node, s, m, idx, v);
	upd(2 * node + 1, m + 1, e, idx, v);
	tree[node] = tree[2 * node] + tree[2 * node + 1];
}

// find kth val
int find(int node, int s, int e, int k) {
	if (s == e) return s;
	int m = (s + e) / 2;
	if (k <= tree[2 * node]) return find(2 * node, s, m, k);
	else return find(2 * node + 1, m + 1, e, k - tree[2 * node]);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	while (n--) {
		cin >> T >> x;
		if (T == 1) upd(1, 1, MAX, x, 1);
		else {
			int del = find(1, 1, MAX, x);
			cout << del << '\n';
			upd(1, 1, MAX, del, -1);
		}
	}
}