n連勤 [yukicoder No.674] - はまやんはまやんはまやん

前提知識

遅延セグメントツリー（区間代入、区間総和）

解法

閉区間でクエリが与えられているが、開区間に直しておこう。
次に、座標圧縮して、日付を2Q個まで減らしておこう。
クエリ更新の度に答えが更新される恐れがあるが、以下の手順で行う。
1. 遅延セグメントツリーを使って、区間に1を代入する
2. 更新した区間の左右それぞれについて、1が続いている個数を二分探索で探す
3. 左から右の長さを求め、それが今までの答えより大きければ更新する。
これを各クエリについて行っていく。

ll D; int Q; ll A[30101], B[30101];
LazySegTree<ll, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> D >> Q;
    rep(i, 0, Q) cin >> A[i] >> B[i];
    rep(i, 0, Q) B[i]++;

    vector<ll> dic;
    rep(i, 0, Q) dic.push_back(A[i]), dic.push_back(B[i]);
    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());

    ll ans = 0;
    rep(q, 0, Q) {
        int a = lower_bound(all(dic), A[q]) - dic.begin();
        int b = lower_bound(all(dic), B[q]) - dic.begin();

        st.update(a, b, 1);

        int L, R;

        { // for L
            int ng = -1, ok = a;
            while (ng + 1 != ok) {
                int md = (ng + ok) / 2;
                if (st.get(md, a + 1) == a + 1 - md) ok = md;
                else ng = md;
            }
            L = ok;
        }

        { // for R
            if (st.get(b, b + 1) == 0) {
                R = b;
            }
            else {
                int ok = b, ng = 1 << 17;
                while (ok + 1 != ng) {
                    int md = (ok + ng) / 2;
                    if (st.get(b, md + 1) == md - b + 1) ok = md;
                    else ng = md;
                }

                R = ng;
            }
        }

        chmax(ans, dic[R] - dic[L]);
        printf("%lld\n", ans);
    }