개념

<aside> 📙

세그먼트 트리에 저장되는 값이 그 값의 개수라고 했을 때

현재 존재하는 수 중 $k$번째로 큰 값을 찾는 방법

• 내 왼쪽 자식노드의 값이 $k$보다 크거나 같으면 내가 찾으려는 값은 왼쪽에 있다.
• 아니라면 오른쪽에 있다.
• 왼쪽으로 내려갈 때는 $k$ 그대로 내려가지만 오른쪽으로 내려갈 땐 왼쪽 노드의 값만큼 빼고 내려가야 한다. </aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

class Seg
{
    private:
        int n;
        vector<int> tree;

        void upd(int node, int start, int end, int idx, int val)
        {
            if(idx<start || end<idx) return;
            if(start == end){
                tree[node] += val;
                return;
            }

            int mid = start+end>>1;
            upd(2*node, start, mid, idx, val);
            upd(2*node+1, mid+1, end, idx, val);
            tree[node] = tree[2*node]+tree[2*node+1];
        }

        int qry(int node, int start, int end, int cnt)
        {
            if(start == end) return start;
            int mid = start+end>>1;
            if(tree[2*node]>=cnt) return qry(2*node, start, mid, cnt);
            else return qry(2*node+1, mid+1, end, cnt-tree[2*node]);
        }

    public:
        Seg(int _n)
        {
            this->n = _n;
            tree.resize(4*n, 0);
        }

        void upd(int idx, int val) { upd(1, 1, n, idx, val); }
        int qry(int cnt) { return qry(1, 1, n, cnt); }
};

signed main()
{
    FASTIO;
    Seg seg(1'000'000);

    int n;
    cin >> n;
    for(int i = 0; i<n; i++){
        int a, b, c;
        cin >> a >> b;
        if(a == 1){
            int ans = seg.qry(b);
            cout << ans <<"\\n";
            seg.upd(ans, -1);
        }
        else{
            cin >> c;
            seg.upd(b, c);
        }
    }
    
    return 0;
}