【ABC217】D - Cutting Woods

atcoder.jp

木を切る問題が出ると二分探索を思い出す。

解法

データ構造に切断点の位置を挿入しながら、二分探索をする。

二分探索をして、切断点の左端と右端がどこかを高速に調べることができる。
二分探索をするにはソートされている必要があるので、挿入時に数字の大小によって順序が保たれるデータ構造が必要になる。
C++だと、std::setが使える。

実装

最初に0とLを挿入しておくといい気がする。
答えは、右端-左端になる。
std::setを使う場合は、std::lower_bound()を使うとO(N)になってしまうことに注意する。

void solve(long long L, long long Q, std::vector<long long> c, std::vector<long long> x) {
    set<ll> st;
    st.insert(0);
    st.insert(L);

    REP (i, Q) {
        if (c[i] == 1) {
            st.insert(x[i]);
        } else {
            auto iter = st.lower_bound(x[i]); // 二分探索
            ll right = *iter; // 右端
            --iter;
            ll left = *iter; // 左端
            cout << right - left << endl;
        }
    }
}