概要

\(N\) 個の部屋を順番に進み、各部屋で「戦闘力が \(A_i\) 以上なら勝利し、戦闘力が \(B_i\) 増加する」というルールでモンスターと戦います。途中で負けるか全勝するまで進むとき、更新クエリ（モンスター情報の変更）と探索クエリ（初期戦闘力 \(s\) で何体倒せるか）を高速に処理する問題です。

考察

1. 素朴なシミュレーションの限界

各探索クエリに対して、部屋 1 から順番にシミュレーションを行うと、1 回のクエリに最大 \(O(N)\) かかります。クエリ数が \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となり、制約（\(N, Q \leq 2 \times 10^5\)）下では実行時間制限に間に合いません。

2. 区間の情報の統合

複数の部屋をまとめた「区間」を考えたとき、その区間を突破するために必要な「最小の初期戦闘力」がわかれば、シミュレーションを加速できそうです。 ある区間について、以下の 2 つの値を保持することを考えます。 - sumB: その区間のモンスターをすべて倒したときに得られる戦闘力の合計値。 - minReq: その区間のモンスターをすべて倒すために、その区間の入り口時点で最低限必要な戦闘力。

2 つの隣接する区間 \(L\)（左側）と \(R\)（右側）を統合して、新しい区間の情報を計算してみましょう。 - new_sumB: \(L.sumB + R.sumB\) （単純な合計） - new_minReq: 1. まず、左側の区間 \(L\) を突破するために \(L.minReq\) が必要です。 2. \(L\) を突破した後の戦闘力は \(s + L.sumB\) になります。これが右側の区間 \(R\) を突破するための条件 \(R.minReq\) を満たす必要があります。 3. つまり、\(s + L.sumB \geq R.minReq \Rightarrow s \geq R.minReq - L.sumB\) となります。 4. したがって、両方を満たすためには \(s \geq \max(L.minReq, R.minReq - L.sumB)\) である必要があります。

このように、区間の情報は「左から順に計算する」という性質を保ったまま統合可能です。

アルゴリズム

セグメント木による解法

区間の情報を管理・更新するためにセグメント木を利用します。

1. 構築・更新: セグメント木の各ノードに {sumB, minReq} を持たせます。葉ノードには各部屋の \(\{B_i, A_i\}\) を格納し、親ノードへ向かって上記の統合式を適用していきます。これにより、1 点更新が \(O(\log N)\) で行えます。

2. 探索（セグメント木上の二分探索）: 初期戦闘力 \(s\) を持って、根ノードから「どこまで進めるか」を判定します。

   • 現在のノードの左側の子供（区間 \(L\)）に注目します。
   • もし \(s \geq L.minReq\) ならば、区間 \(L\) のモンスターはすべて倒せます。戦闘力を \(s \leftarrow s + L.sumB\) と更新し、右側の子供へ進みます。
   • もし \(s < L.minReq\) ならば、区間 \(L\) の途中で倒せなくなるモンスターがいます。そのため、左側の子供の中を詳しく探索します。

この操作を葉に到達するまで繰り返すことで、最初に倒せなくなるモンスターの直前（あるいは全滅させた場所）を \(O(\log N)\) で特定できます。

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • セグメント木の構築に \(O(N)\)、各クエリ（更新・探索）に \(O(\log N)\) かかります。
• 空間計算量: \(O(N)\)
  • セグメント木のノード数は約 \(4N\) です。

実装のポイント

• オーバーフローへの注意: 戦闘力の合計値 sumB は非常に大きくなる可能性があるため、64bit整数型（C++なら long long）を使用する必要があります。

• 番兵（ダミーノード）の活用: セグメント木のサイズを 2 のべき乗（\(2^k \geq N\)）に調整する際、余った葉ノードには minReq として非常に大きな値（無限大）を設定しておくと、探索が \(N\) を超えて進んでしまうのを防ぐことができ、実装がシンプルになります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem Analysis:
 * - Takahashi moves through rooms 1 to N sequentially.
 * - Room i requires combat power A_i to pass and increases combat power by B_i.
 * - If current combat power S < A_i, exploration ends.
 * - Two types of events: update room monster info (A_i, B_i) and query max monsters defeated starting with power s.
 * 
 * Segment Tree Approach:
 * - Each node in the segment tree represents a range of rooms [L, R].
 * - For a range, we store:
 *   1. sumB: The total combat power gained after defeating all monsters in the range.
 *   2. minReq: The minimum initial combat power required to defeat all monsters in the range.
 * - Merging two nodes (left L, right R):
 *   - node.sumB = L.sumB + R.sumB
 *   - node.minReq = max(L.minReq, R.minReq - L.sumB)
 * - To find the maximum monsters defeated, we traverse the segment tree from the root.
 * - If starting power s >= left_child.minReq, we can defeat all monsters in the left child, 
 *   increase s by left_child.sumB, and move to the right child.
 * - Otherwise, we must search within the left child.
 */

// A large value for INF that won't overflow long long when subtracted from.
// Max possible sum of B_i is 2e5 * 1e9 = 2e14.
// Max possible initial s is 1e9. Max s during exploration is 1e9 + 2e14 = 2.00001e14.
// INF = 2e18 is safe because INF - 2e14 is still much larger than any possible s.
const long long INF = 2e18;

struct Node {
    long long sumB;
    long long minReq;
};

int main() {
    // Optimize I/O performance
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    // Determine segment tree size (smallest power of 2 >= N)
    int sz = 1;
    while (sz < N) sz *= 2;

    // tree[1] is the root, leaves are from tree[sz] to tree[sz + N - 1].
    // Dummy nodes (indices >= sz + N) are initialized with INF minReq to ensure 
    // the traversal correctly identifies the end of the dungeon.
    vector<Node> tree(2 * sz, {0, INF});

    // Read initial monster data and place them in the leaves
    for (int i = 0; i < N; ++i) {
        long long a, b;
        cin >> a >> b;
        tree[sz + i] = {b, a};
    }

    // Build the segment tree from leaves up to the root in O(N)
    for (int i = sz - 1; i >= 1; --i) {
        tree[i].sumB = tree[2 * i].sumB + tree[2 * i + 1].sumB;
        tree[i].minReq = max(tree[2 * i].minReq, tree[2 * i + 1].minReq - tree[2 * i].sumB);
    }

    // Process Q events
    for (int q = 0; q < Q; ++q) {
        int type;
        cin >> type;
        if (type == 1) {
            // Type 1: Update room i's monster info
            int i;
            long long a, b;
            cin >> i >> a >> b;
            int idx = i - 1 + sz;
            tree[idx] = {b, a};
            idx /= 2;
            // Propagate updates up to the root in O(log N)
            while (idx >= 1) {
                tree[idx].sumB = tree[2 * idx].sumB + tree[2 * idx + 1].sumB;
                tree[idx].minReq = max(tree[2 * idx].minReq, tree[2 * idx + 1].minReq - tree[2 * idx].sumB);
                idx /= 2;
            }
        } else {
            // Type 2: Query max monsters defeated starting with combat power s
            long long s;
            cin >> s;
            int curr = 1;
            // Traverse the segment tree in O(log N) to find the first monster that cannot be defeated
            while (curr < sz) {
                if (s >= tree[2 * curr].minReq) {
                    // Can defeat all monsters in the left child's range
                    s += tree[2 * curr].sumB;
                    curr = 2 * curr + 1;
                } else {
                    // Cannot defeat all monsters in the left child's range, so move into it
                    curr = 2 * curr;
                }
            }
            // Now curr is a leaf index (sz to 2*sz-1). 
            // Check if the monster at this leaf is defeated.
            int ans;
            if (s >= tree[curr].minReq) {
                // If this monster is defeated, Takahashi defeated monsters 1 to (curr - sz + 1)
                ans = curr - sz + 1;
            } else {
                // If not, Takahashi defeated monsters 1 to (curr - sz)
                ans = curr - sz;
            }
            // Ensure the answer does not exceed N (especially if sz > N)
            if (ans > N) ans = N;
            cout << ans << "\n";
        }
    }

    return 0;
}

---

この解説は gemini-3-flash-thinking によって生成されました。