사탕상자

#include <iostream>
#include <vector>
#include <cmath>
 
#define MAXX 1000001
using namespace std;
 
typedef long long ll;
int tree_h;
int ret = 0;
 
void update(vector<int> &tree, int node, int diff, int idx, int start, int end) {
    if (idx < start || end < idx) {
        return;
    }
    tree[node] += diff;
    if (start != end) {
        update(tree, node*2, diff, idx, start, (start+end)/2);
        update(tree, node*2+1, diff, idx, (start+end)/2+1, end);
    }
}
int query(vector<int> & tree, int node, int idx, int start, int end) {
    if (start == end ) {
       
        return start;
    }
    //왼쪽에 idx개 이상의 노드가 있으면 그쪽으로 탐색한다. 
    if ((node*2 <= tree_h && tree[node*2] >= idx)) {
        //사탕의 맛 순서대로, 개수만큼 정렬되어있기 때문에 idx보다 지금 가르키는 노드의 값이 크다면 왼쪽에 그만큼 사탕이 존재하다는 것이다. 
        //즉, 1번 사탕이 3개 / 3번 사탕이 4개 있다면 
        //세그먼트 트리의 리프노드는 
        //1113333 이 될 것이다. 
        return ret = query(tree, node*2, idx, start, (start+end)/2);
    }
    
    idx -= tree[node*2]; //왼쪽에 없으니까 왼쪽에 있는 개수만큼 빼준다.  
    
    //오른쪽 탐색 
    if ((node*2+1 <= tree_h && tree[node*2+1] >= idx)) {
        return ret = query(tree, node*2+1, idx, (start+end)/2+1, end);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    int h = (int)ceil(log2(MAXX));
    tree_h = 1 << (h+1);
 
    vector<int> tree(tree_h);
 
    while(n--) {
        int a, b,c;
        cin >> a;
 
        if (a == 1) {
            //사탕을 꺼낸다. 
            cin >> b;
            //사탕의 순위 
 
            int taste = query(tree, 1, b, 0, MAXX-1);
            cout <<taste << '\n';
            update(tree, 1, -1, taste, 0, MAXX-1);
        }
        else {
            cin >> b >> c;
            //b는 넣을 사탕의 맛 
            //c가 양수면 넣고 음수면 뺀다. 
            update(tree, 1, c, b, 0, MAXX-1);
        }
       
    }
    return 0;
}