[백준] 12899 데이터 구조

세그먼트트리에서 K번째를 찾는 유형의 문제

200만개의 배열을 미리 잡아두고

쿼리가 1로 들어오면 그 숫자를 인덱스로 보고

배열에서 인덱스를 찾아가 1업데이트 시켜준다

세그먼트트리는 합으로 만들어준다

쿼리가 2라면 K번째를 찾아가자..!

그리고 -1로 업데이트해서 삭제시킨다

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 2000020;
int n;
void update(vector<int>&tree, int node, int start, int end, int index,int val) {
    if (index < start || index > end) return;
    if (start == end) {
        tree[node] +=val; return;
    }
    update(tree, node * 2, start, (start + end) / 2, index,val);
    update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index,val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int Kth(vector<int>&tree, int node, int start, int end, int k) {
    if (start == end) return start;
    else {
        if (k <= tree[node * 2]) return Kth(tree, node * 2, start, (start + end) / 2, k);
        else return Kth(tree, node * 2+1, (start + end) / 2 + 1, end, k - tree[node * 2]);
    }
}
int main() {
    scanf(" %d", &n);
    int h = (int)ceil(log2(MAXN + 1));
    int tree_size = (1 << (h + 1));
    vector<int> a(MAXN,0), tree(tree_size,0);
    for (int i = 0; i < n; i++) {
        int x, y; scanf(" %d %d", &x, &y);
        if (x == 1) update(tree, 1, 1, 2000002, y,1);
        else {
            int pos = Kth(tree, 1, 1, 2000002, y);
            update(tree, 1, 1, 2000002, pos, -1);
            printf("%d\n", pos);
        }
    }
}