概要

各部屋を「倒すための必要戦闘力 \(A_i\)」「倒した後の増加量 \(B_i\)」として管理し、
更新クエリと「先頭から何部屋倒せるか」という問い合わせを高速に処理する問題です。
セグメント木に「区間を全突破するのに必要な初期戦闘力」を持たせることで、各クエリを \(O(\log N)\) で処理できます。

考察

この問題の本質は、ある区間をまとめて見たときに

• その区間を全部倒すと戦闘力がどれだけ増えるか
• その区間を最初から最後まで突破するために、開始時点で最低いくつ必要か

をうまく合成できるか、です。

1. 1部屋なら情報は簡単

部屋 \(i\) だけなら、

• 総増加量：\(B_i\)
• 必要初期戦闘力：\(A_i\)

です。

2. 2つの連続区間を結合する

左区間を \(L\)、右区間を \(R\) とします。

• 左を突破すると戦闘力が \(L.sumB\) 増える
• 右を突破するには「右に入る時点」で \(R.need\) 必要

つまり「全体の開始時点」で必要なのは
\(R.need - L.sumB\) 以上です（左で増えた分だけ要求が下がる）。

したがって結合区間の必要初期戦闘力は

\[ need = \max(L.need,\; R.need - L.sumB) \]

総増加量は

\[ sumB = L.sumB + R.sumB \]

この2つがあれば、区間情報を合成できます。

---

素朴にクエリ 2 s ごとに部屋1から順にシミュレーションすると、最悪で1クエリ \(O(N)\)、全体で \(O(NQ)\) となり制約に間に合いません。
そこでセグメント木を使い、更新と問い合わせをどちらも \(O(\log N)\) に落とします。

アルゴリズム

各セグメント木ノードに以下を持たせます。

• sumB: その区間を全突破したときの増加量合計
• need: その区間を全突破するのに必要な最小初期戦闘力

マージ

左右ノード L, R から

• sumB = L.sumB + R.sumB
• need = max(L.need, R.need - L.sumB)

更新クエリ 1 i a b

葉（部屋 \(i\)）を sumB=b, need=a に置き換え、上に再計算。
計算量 \(O(\log N)\)。

問い合わせクエリ 2 s

求めたいのは「初期戦闘力 \(s\) で倒せる先頭からの最大部屋数」。

• もし根の need <= s なら全 \(N\) 部屋倒せる。
• そうでなければ、セグメント木を上から降りる。
  • これまでに確定で倒せる左側の増加量を gain とする。
  • 左子区間を全突破可能かは
    left.need - gain <= s で判定できる。
    • 可能なら左を丸ごと取り、gain += left.sumB して右へ。
    • 不可能なら左へ降りる。
• 葉に着いたときの位置から、最大 prefix 長を得る。

これで問い合わせも \(O(\log N)\) です。

計算量

• 時間計算量: \(O((N+Q)\log N)\)（構築 \(O(N)\)、各クエリ \(O(\log N)\)）
• 空間計算量: \(O(N)\)（セグメント木）

実装のポイント

• 空区間の単位元として sumB=0, need=-INF を使うとマージが自然に書けます。

• A_i, B_i や合計値は大きくなるので long long を使います。

• prefix探索で使う判定は
  left.need - gain <= s
  という「すでに得た増加量で必要値を引く」形にするのが重要です。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (1LL << 62);

struct Node {
    ll sumB;   // total gain
    ll need;   // minimum initial power needed to clear this segment
};

Node mergeNode(const Node& L, const Node& R) {
    Node res;
    res.sumB = L.sumB + R.sumB;
    // need for right segment in terms of initial at whole segment: needR - gainLeft
    ll shiftedR = R.need - L.sumB;
    res.need = max(L.need, shiftedR);
    return res;
}

struct SegTree {
    int n;
    vector<Node> st;

    SegTree(int sz = 0) { init(sz); }

    void init(int sz) {
        n = 1;
        while (n < sz) n <<= 1;
        st.assign(2 * n, Node{0, -INF}); // identity for merge on empty segment
    }

    void build(const vector<ll>& A, const vector<ll>& B) {
        int sz = (int)A.size();
        for (int i = 0; i < sz; i++) {
            st[n + i] = Node{B[i], A[i]};
        }
        for (int i = n - 1; i >= 1; i--) {
            st[i] = mergeNode(st[i << 1], st[i << 1 | 1]);
        }
    }

    void point_update(int idx, ll a, ll b) {
        int p = n + idx;
        st[p] = Node{b, a};
        p >>= 1;
        while (p) {
            st[p] = mergeNode(st[p << 1], st[p << 1 | 1]);
            p >>= 1;
        }
    }

    // maximum prefix length k such that initial s can clear first k rooms
    int maxPrefix(ll s, int N) const {
        if (N == 0) return 0;
        if (st[1].need <= s) return N;

        int v = 1, l = 0, r = n;
        ll gain = 0;
        while (v < n) {
            int lc = v << 1, rc = lc | 1;
            int mid = (l + r) >> 1;

            const Node& L = st[lc];
            // can clear whole left with current initial adjusted by gained?
            // condition: s >= max(prefix_need, ...) -> here for segment with prior gain=gain:
            // need segment under original initial is L.need - gain
            if (L.need - gain <= s) {
                gain += L.sumB;
                v = rc;
                l = mid;
            } else {
                v = lc;
                r = mid;
            }
        }
        return min(l, N);
    }
};

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

    int N, Q;
    cin >> N >> Q;

    vector<ll> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];

    SegTree seg(N);
    seg.build(A, B);

    for (int qi = 0; qi < Q; qi++) {
        int t;
        cin >> t;
        if (t == 1) {
            int i;
            ll a, b;
            cin >> i >> a >> b;
            --i;
            seg.point_update(i, a, b);
        } else {
            ll s;
            cin >> s;
            cout << seg.maxPrefix(s, N) << '\n';
        }
    }

    return 0;
}

---

この解説は gpt-5.3-codex によって生成されました。