AtCoder Regular Contest 021 ARC021 C - データ構造

atcoder.jp

類題がこれ。

coonevo.hatenablog.com

ライブラリでやるだけ。

template<typename T>
class BIT{
  public:


    int N;
    vector<T> data;
    BIT(T _N):N(_N){
        data.assign(N+1, 0);
    };
    
    // a is 1-indexed
    void add(int a, T w){
        for(int x = a; x <= N; x += x & -x)data[x] += w;
    }
    // 1-indexed sum of prefix [0, a]
    T sum(int a){
        T res = 0;
        for(int x = a; x > 0; x -= x & -x)res += data[x];
        return res;
    }
    // 1-indexed sum of range [l, r]
    T sum(int l, int r){return sum(r) - sum(l-1);}

    // 0-indexed add
    void add0(int a, T w){add(a + 1, w);}
    // 0-indexed sum
    T sum0(int a){return sum(a + 1);}
    // 0-indexed sum of range
    T sum0(int l, int r){return sum0(r) - sum0(l-1);}
    // show the value
    void debug(){print(data);}
    // k-th number (k is 1 - indexed)
    T get(int k){
        T res = 0;
        int sz = 1;
        while(sz < (int)data.size()) sz <<= 1;
        for(int i = sz / 2; i > 0; i >>= 1){
            if(res + i <= N && data[res + i] < k){
                k -= data[res + i];
                res += i;
            }
        }
        return res + 1;
    }
};

int main() {

    BIT<ll> B(200010);
    int Q;
    cin >> Q;
    while(Q--){
        int t, x;
        cin >> t >> x;
        if(t == 1){
            B.add(x,1);
        }
        if(t == 2){
            int k = B.get(x);
            cout << k << endl;
            B.add(k,-1);
        }
    }
}