概要

各挑戦について、初期戦闘力 \(s\) で何部屋目まで進めるかを求めます。
部屋情報の更新もあるため、毎回先頭からシミュレーションするのではなく、セグメント木を使って高速に処理します。

考察

部屋 \(i\) に入る前までに得られる戦闘力の増加量を考えます。

部屋 \(i\) に到達する前に倒しているのは部屋 \(1,2,\ldots,i-1\) のモンスターなので、その時点での戦闘力は

\( s + \sum_{j=1}^{i-1} B_j \)

です。

部屋 \(i\) のモンスターを倒すには、これが \(A_i\) 以上である必要があります。

つまり、

\( s + \sum_{j=1}^{i-1} B_j \geq A_i \)

です。

これを変形すると、

\( s \geq A_i - \sum_{j=1}^{i-1} B_j \)

となります。

ここで、

\( C_i = A_i - \sum_{j=1}^{i-1} B_j \)

と定義します。

すると、部屋 \(i\) を倒せる条件は単に

\( s \geq C_i \)

になります。

したがって、初期戦闘力 \(s\) で探索したときに最初に倒せない部屋は、

\( C_i > s \)

となる最小の \(i\) です。

そのような部屋が存在しなければ、すべての \(N\) 体を倒せます。

例えば、

• \(A = [3,5,10]\)
• \(B = [2,4,1]\)

のとき、

• 部屋 \(1\) の前に得ている増加量は \(0\)
• 部屋 \(2\) の前に得ている増加量は \(2\)
• 部屋 \(3\) の前に得ている増加量は \(2+4=6\)

なので、

\( C = [3-0, 5-2, 10-6] = [3,3,4] \)

です。

初期戦闘力 \(s=3\) の場合、最初に \(C_i > 3\) となるのは部屋 \(3\) なので、倒せる数は \(2\) です。

素朴に各クエリで部屋 \(1\) から順にシミュレーションすると、1 回のクエリに \(O(N)\) かかります。
\(N,Q\) が最大 \(2 \times 10^5\) 程度あるため、これは間に合いません。

そこで、配列 \(C\) を管理し、次の操作を高速に行えるようにします。

• 区間に値を加算する
• 最初に \(C_i > s\) となる位置を探す

これは遅延伝播付きセグメント木で実現できます。

アルゴリズム

まず、配列 \(C\) を作ります。

0-indexed で考えると、部屋 \(i\) に入る前の増加量は

\( B_0 + B_1 + \cdots + B_{i-1} \)

なので、

\( C_i = A_i - \sum_{j=0}^{i-1} B_j \)

です。

更新クエリ

部屋 \(i\) の情報が

\( (A_i, B_i) \to (a,b) \)

に変わるとします。

差分を

• \(da = a - A_i\)
• \(db = b - B_i\)

とします。

\(A_i\) の変更の影響

\(C_i\) は \(A_i\) を含むので、部屋 \(i\) の \(C_i\) だけが \(da\) だけ変化します。

つまり、

\( C_i \leftarrow C_i + da \)

です。

\(B_i\) の変更の影響

\(B_i\) は、部屋 \(i+1\) 以降に入る前の累積増加量に影響します。

\(B_i\) が \(db\) 増えると、部屋 \(i+1\) 以降では事前に得られる戦闘力が \(db\) 増えます。
そのため、

\( C_j = A_j - \sum_{k<j} B_k \)

は、\(j > i\) について \(db\) だけ小さくなります。

つまり、

\( C_j \leftarrow C_j - db \quad (j > i) \)

です。

したがって、更新は次の 2 つになります。

• \(C_i\) に \(da\) を加算
• 区間 \([i+1, N)\) に \(-db\) を加算

挑戦クエリ

初期戦闘力 \(s\) に対して、最初に

\( C_i > s \)

となる位置を探します。

その位置が存在しなければ、すべてのモンスターを倒せるので答えは \(N\) です。

存在する場合、その部屋で倒せず終了するので、倒せる数はその位置の index になります。

例えば 0-indexed で最初に条件を満たす位置が pos なら、倒せる数は pos です。

セグメント木で管理する値

セグメント木の各ノードには、その区間の \(C_i\) の最大値を持たせます。

ある区間の最大値が \(s\) 以下なら、その区間には \(C_i > s\) となる要素は存在しません。

逆に最大値が \(s\) より大きければ、その区間のどこかに倒せない部屋があります。

その性質を使って、セグメント木を上から辿ることで、最初に \(C_i > s\) となる位置を \(O(\log N)\) で見つけられます。

計算量

• 時間計算量: \(O((N+Q)\log N)\)
  • 初期構築は \(O(N)\)
  • 各更新クエリは区間加算を 2 回行うので \(O(\log N)\)
  • 各挑戦クエリも \(O(\log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 累積和や \(C_i\) の値は最大で \(10^9 \times 2 \times 10^5\) 程度になるため、long long を使います。

• セグメント木では、区間加算に対応するために lazy 配列を持ちます。

• first_greater(s) では、まず全体の最大値が \(s\) 以下なら答えは存在しません。

• 存在する場合は、左の子の最大値が \(s\) より大きいなら左へ、そうでなければ右へ進むことで、最小の位置を探します。

• 更新時、\(B_i\) の変更は部屋 \(i\) 自身には影響せず、部屋 \(i+1\) 以降だけに影響することに注意します。

  ソースコード

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

using ll = long long;

struct SegTree {
    int n;
    vector<ll> mx, lazy;

    SegTree(const vector<ll>& v) {
        int sz = (int)v.size();
        n = 1;
        while (n < sz) n <<= 1;
        mx.assign(2 * n, LLONG_MIN / 4);
        lazy.assign(2 * n, 0);
        for (int i = 0; i < sz; i++) mx[n + i] = v[i];
        for (int i = n - 1; i >= 1; i--) mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
    }

    void apply(int k, ll x) {
        mx[k] += x;
        lazy[k] += x;
    }

    void push(int k) {
        if (lazy[k] != 0) {
            apply(k << 1, lazy[k]);
            apply(k << 1 | 1, lazy[k]);
            lazy[k] = 0;
        }
    }

    void range_add(int a, int b, ll x, int k, int l, int r) {
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            apply(k, x);
            return;
        }
        push(k);
        int m = (l + r) >> 1;
        range_add(a, b, x, k << 1, l, m);
        range_add(a, b, x, k << 1 | 1, m, r);
        mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
    }

    void range_add(int l, int r, ll x) {
        if (l >= r) return;
        range_add(l, r, x, 1, 0, n);
    }

    int first_greater(ll x) {
        if (mx[1] <= x) return -1;
        int k = 1, l = 0, r = n;
        while (r - l > 1) {
            push(k);
            int m = (l + r) >> 1;
            if (mx[k << 1] > x) {
                k = k << 1;
                r = m;
            } else {
                k = k << 1 | 1;
                l = m;
            }
        }
        return l;
    }
};

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

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

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

    ll pref = 0;
    for (int i = 0; i < N; i++) {
        C[i] = A[i] - pref;
        pref += B[i];
    }

    SegTree seg(C);

    while (Q--) {
        int t;
        cin >> t;

        if (t == 1) {
            int i;
            ll a, b;
            cin >> i >> a >> b;
            --i;

            ll da = a - A[i];
            ll db = b - B[i];

            A[i] = a;
            B[i] = b;

            seg.range_add(i, i + 1, da);
            seg.range_add(i + 1, N, -db);
        } else {
            ll s;
            cin >> s;

            int pos = seg.first_greater(s);
            if (pos == -1) cout << N << '\n';
            else cout << pos << '\n';
        }
    }

    return 0;
}

---

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