BOJ 12899 데이터 구조

1 개요

BOJ 12899 데이터 구조

• 백준 온라인 저지 12899번 문제
• BOJ 45단계

2 C++

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

const int MAX = 2000000;
vector<int> tree(4 * MAX);

void update(int node, int start, int end, int idx, int val) {
    if (idx < start || idx > end) return;
    tree[node] += val;
    if (start != end) {
        int mid = (start + end) / 2;
        update(node * 2, start, mid, idx, val);
        update(node * 2 + 1, mid + 1, end, idx, val);
    }
}

int query(int node, int start, int end, int k) {
    if (start == end) return start;
    int mid = (start + end) / 2;
    if (k <= tree[node * 2]) return query(node * 2, start, mid, k);
    else return query(node * 2 + 1, mid + 1, end, k - tree[node * 2]);
}

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

    int N, T, X;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> T >> X;
        if (T == 1) {
            update(1, 1, MAX, X, 1);
        } else {
            int result = query(1, 1, MAX, X);
            cout << result << "\n";
            update(1, 1, MAX, result, -1);
        }
    }
}