AtCoder ABC217 D - Cutting Woods 解

##問題概要
区間 $[0,L]$ に対して以下2種類のクエリを順に施した結果を出力せよ。クエリは合計で $Q$ 個ある。

1. 指定された $x=0,1,2,...,L-1$ で区間を分割する
2. $x$ の属する区間長を出力する

• 主な制約
• $1 \le L \le 10^9 $
• $1 \le Q \le 2 \times 10^5 $

##考察
※公式解説が十分すぎるほど詳しい。

出力対象である $x$ の属する区間長を求めるには、$x$ を挟む（最寄りの）区間の切れ目を検索できれば良い。その検索速度は、$Q$ の大きさ的に$\log Q$ のオーダーまでは許容できるので、二分探索で乗り切りたい。そのためには、lower_bound 関数などを適用できるデータ構造に切れ目の情報を入れておきたい。すると set が自然と浮かぶ。

この方針で実装したときの時間計算量が $Q \log Q$ のオーダーに収まることは（直感的にはいけそうだが）非自明なので一応確かめておくべき。ありがたいことに公式解説にある。

##実装
set に対して lower_bound を当てるときは set のメソッドとして set.lower_bound(queried_value)のように呼ばないと遅くなるっぽいので注意。 ここをミスって一度 TLE を出した。

lower_bound の返り値が set.begin() や set.end() になると処理が面倒なので $0$ と $L$ に切れ目があるというダミー情報を set に入れておいた。

#define rp(i, n) for (int i = 0; i < n; ++i)
#define print(x) std::cout << (x) << std::endl;
int main() {
    // read input
    auto L = in<ll>();
    auto Q = in<ll>();
    set<ll> cut;
    cut.insert(0);
    cut.insert(L);
    rp(i, Q) {
        auto c = in<ll>();
        auto x = in<ll>();
        if (c == 1) {
            cut.insert(x);
        } else {
            auto r = cut.lower_bound(x);
            auto l = prev(r, 1);
            print(*r - *l);
        }
    }
}