백준 12899 (C++) 데이터 구조

최초 업로드: 2025-04-19 08:48:59

최근 수정 시간: 2025-07-25 09:38:54

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] 데이터 구조

#### [문제 링크](https://www.acmicpc.net/problem/12899)

## 문제 설명

자연수를 저장하는 데이터베이스 S에 대해 다음의 쿼리를 처리합시다.

유형 1 : S에 자연수 X를 추가한다.

유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 수를 삭제한다.

## 입력

첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000)

둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다.

T가 1이라면 S에 추가할 X가 주어지는 것입니다. (1 ≤ X ≤ 2,000,000)

T가 2라면 X는 S에서 삭제해야 할 몇 번째로 작은 수인지를 나타냅니다. S에 최소 X개의 원소가 있음이 보장됩니다.

## 출력

유형 2의 쿼리 개수만큼의 줄에 각 쿼리에 대한 답을 출력합니다.

## 풀이
#### cnt를 L~R까지 숫자의 등장 횟수로 두고, 입력받은 숫자번째의 cnt값을 증가시키면서 세그먼트 트리를 쓰면 풀린다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 2'000'000;
const int MAX_LEN = MAX*3;
int _size=1, cnt[MAX_LEN];

void update(int nodeNum) {
    while(nodeNum>1) {
        nodeNum/=2;
        cnt[nodeNum] = cnt[nodeNum*2]+cnt[nodeNum*2+1];
    }
}

int search(int nodeNum, int nodeL, int nodeR, int pos) {
 if(nodeL==nodeR) {
 cnt[nodeNum]--;
 update(nodeNum);
 return nodeL;
 }
 int mid = (nodeL+nodeR)/2;
 if(pos<=cnt[nodeNum*2]) return search(nodeNum*2, nodeL, mid, pos);
 return search(nodeNum*2+1, mid+1, nodeR, pos-cnt[nodeNum*2]);
}

void insert(int val) {
    int nodeNum = val+_size/2;
    cnt[nodeNum]++;
    update(nodeNum);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 while(_size<MAX) _size<<=1;
 _size<<=1;

while(n--) {
 int q, x; cin >> q >> x;
 if(q==1) {
 insert(x);
 } else {
 cout << search(1, 0, _size/2-1, x) << '\n';
 }
 }
}
```