Overview

For each challenge, we determine how many rooms can be cleared starting with an initial power of \(s\).
Since room information can be updated, instead of simulating from the beginning each time, we use a segment tree for efficient processing.

Analysis

Consider the cumulative increase in power gained before entering room \(i\).

Before reaching room \(i\), the monsters in rooms \(1, 2, \ldots, i-1\) have already been defeated, so the power at that point is

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

To defeat the monster in room \(i\), this must be at least \(A_i\).

That is,

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

Rearranging this, we get

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

Here, we define

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

Then, the condition to defeat room \(i\) is simply

\( s \geq C_i \)

Therefore, the first room that cannot be defeated when exploring with initial power \(s\) is the smallest \(i\) such that

\( C_i > s \)

If no such room exists, all \(N\) monsters can be defeated.

For example, if

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

then,

• The cumulative increase before room \(1\) is \(0\)
• The cumulative increase before room \(2\) is \(2\)
• The cumulative increase before room \(3\) is \(2+4=6\)

so,

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

For initial power \(s=3\), the first \(C_i > 3\) occurs at room \(3\), so the number of monsters defeated is \(2\).

If we naively simulate from room \(1\) for each query, each query takes \(O(N)\).
Since \(N, Q\) can be up to about \(2 \times 10^5\), this is too slow.

Therefore, we maintain the array \(C\) and support the following operations efficiently:

• Add a value to a range
• Find the first position where \(C_i > s\)

This can be achieved with a segment tree with lazy propagation.

Algorithm

First, we construct the array \(C\).

Using 0-indexed notation, the cumulative increase before entering room \(i\) is

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

so,

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

Update Query

Suppose the information for room \(i\) changes from

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

Let the differences be

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

Effect of changing \(A_i\)

Since \(C_i\) includes \(A_i\), only \(C_i\) for room \(i\) changes by \(da\).

That is,

\( C_i \leftarrow C_i + da \)

Effect of changing \(B_i\)

\(B_i\) affects the cumulative increase before entering rooms \(i+1\) and beyond.

If \(B_i\) increases by \(db\), the power gained before entering rooms \(i+1\) and beyond increases by \(db\).
Therefore,

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

decreases by \(db\) for all \(j > i\).

That is,

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

Thus, the update consists of two operations:

• Add \(da\) to \(C_i\)
• Add \(-db\) to the range \([i+1, N)\)

Challenge Query

For initial power \(s\), find the first position where

\( C_i > s \)

If no such position exists, all monsters can be defeated, so the answer is \(N\).

If such a position exists, the challenge ends at that room, so the number of monsters defeated equals the index of that position.

For example, in 0-indexed terms, if the first position satisfying the condition is pos, then the number defeated is pos.

Values Managed by the Segment Tree

Each node of the segment tree stores the maximum value of \(C_i\) in its interval.

If the maximum value of an interval is at most \(s\), then no element in that interval satisfies \(C_i > s\).

Conversely, if the maximum is greater than \(s\), then somewhere in that interval there is a room that cannot be cleared.

Using this property, by traversing the segment tree from top to bottom, we can find the first position where \(C_i > s\) in \(O(\log N)\).

Complexity

• Time complexity: \(O((N+Q)\log N)\)
  • Initial construction is \(O(N)\)
  • Each update query performs range addition twice, so \(O(\log N)\)
  • Each challenge query is also \(O(\log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Prefix sums and values of \(C_i\) can be as large as about \(10^9 \times 2 \times 10^5\), so use long long.

• The segment tree uses a lazy array to support range addition.

• In first_greater(s), if the overall maximum is at most \(s\), then no such position exists.

• If it does exist, go to the left child if the left child’s maximum is greater than \(s\); otherwise, go to the right child. This finds the minimum position.

• When updating, note that a change to \(B_i\) does not affect room \(i\) itself, but only affects rooms \(i+1\) and beyond.

  Source Code

#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;
}

---

This editorial was generated by gpt-5.5-xhigh.