ARC033 C問題

数を加えるか、n番目に小さい値を出力して、その数を削除するか、の２つのクエリを処理するだけの問題。
簡単だけど、２分探索のところで少しバグらせてしまった。
友人曰く大事なのは
highとlowどちらが合ってるのか、を理解すること。
今回だったら、lowは条件を満たしていないから、正しいのはhigh。
そこを考えてlow, highの初期値を選んであげる

struct BinaryIndexedTree{
    int N;
    std::vector<int> bit; //1-indexed つまり1~Nを使う
    BinaryIndexedTree(int n): N(n), bit(n+1, 0){}
    void add(int a, int w){
        for(int x = a; x <=N; x+=x&(-x)) bit[x] += w;
    }
    int sum(int a){ //1~aまでsum
        int ret = 0;
        for(int x = a; x>0; x-=x&(-x)) ret += bit[x];
        return ret;
    }
};

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

    BinaryIndexedTree BIT(200001);
    int Q; cin >> Q;
    for(int i=0; i<Q; i++){
        int t, x;
        cin >> t >> x;
        if(t == 1){
            BIT.add(x, 1);
        }else{
            int low = 0, high = 200000;
            while(high - low > 1){
                int mid = (low+high)/2;
                if(BIT.sum(mid) < x){
                    low = mid;
                }else{
                    high = mid;
                }
            }
            cout << high << endl;
            BIT.add(high, -1);
        }
    }
}