[백준] 데이터 구조

세그먼트 트리를 이용해서 숫자를 추가하고 N번째로 작은 숫자를 찾고 제거하는 문제이다.
이때 문제를 풀때 특정 숫자를 계속 추가하고 N번째로 작은 숫자를 찾아 제거 해야하는데, 세그먼트 트리 구조를 사용하기 위해서는 고정된 길이를 가진 상태여야한다.
그리고 고정된 길이 안에서 세그먼트 트리의 노드에 현재 입력된 숫자들의 개수를 합산하여 저장한다.

리프 노드에는 추가된 숫자의 개수정보를 담게 되고 내부 노드는 각 범위의 총 개수를 담게된다.
이제 특정 순번의 숫자를 제거할 때, 앞 노드와 순번을 비교해나가면서 해당 위치를 찾아 가면된다.

#include<iostream>

using namespace std;

int seg_tree[2 << 22];
int del_num;


int update(int left,int right,int target,int depth) {
	if (right < target || left>target) return seg_tree[depth];
	if (left == right && left == target) return seg_tree[depth] += 1;

	int mid = (left + right) / 2;

	int set1 = update(left, mid, target, depth * 2);
	int set2 = update(mid + 1, right, target, depth * 2 + 1);

	return seg_tree[depth] = set1 + set2;
}

int del(int left, int right, int target, int depth) {

	if (left == right) {
		del_num = left;
		return seg_tree[depth]  -= 1;
	}

	int mid = (left + right) / 2;

	if (seg_tree[depth*2] < target) {
		target -= seg_tree[depth*2];

		int set1 = seg_tree[depth * 2];
		int set2 = del(mid + 1, right, target, depth * 2 + 1);

		return seg_tree[depth] = set1 + set2;
	}
	else {
		int set1 = del(left, mid, target, depth * 2);
		int set2 = seg_tree[depth * 2 + 1];

		return seg_tree[depth] = set1 + set2;
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	int N, T, X;

	cin >> N;

	while (N--) {
		cin >> T >> X;

		if (T == 1) {
			update(1, 2'000'000, X, 1);
		}
		else {
			del(1, 2'000'000, X, 1);
			cout << del_num << "\n";
		}

	}
}