Overview

This problem asks us to efficiently answer “starting with initial power \(s\), how many monsters can you defeat from the beginning?” while room information is being updated.

For each interval, we manage “the minimum initial power required to clear the entire interval” and “the total power gained from defeating all monsters in the interval” using a segment tree.

Analysis

For a contiguous interval of rooms, consider maintaining the following \(2\) values:

• \(\mathrm{sum}\): the total power gained from defeating all monsters in the interval
• \(\mathrm{need}\): the minimum power required before entering the interval to defeat all monsters in it

For example, for an interval consisting of only room \(i\):

• \(\mathrm{sum} = B_i\)
• \(\mathrm{need} = A_i\)

Now, consider splitting the interval into a left half \(L\) and a right half \(R\).

To clear the left half, the initial power must be at least \(\mathrm{need}_L\).

Also, after clearing the left half, the power increases by \(\mathrm{sum}_L\).
To clear the right half, the power at that point must be at least \(\mathrm{need}_R\), so for the initial power \(x\):

\[ x + \mathrm{sum}_L \geq \mathrm{need}_R \]

In other words,

\[ x \geq \mathrm{need}_R - \mathrm{sum}_L \]

is required.

Therefore, the minimum initial power required to clear the entire combined interval is:

\[ \mathrm{need} = \max(\mathrm{need}_L, \mathrm{need}_R - \mathrm{sum}_L) \]

Also, the total power gained is simply:

\[ \mathrm{sum} = \mathrm{sum}_L + \mathrm{sum}_R \]

In this way, the information for an interval can be computed from the information of its left and right child intervals.
Therefore, it can be managed with a segment tree.

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

Instead, we use a segment tree to process:

• Update query: \(O(\log N)\)
• Challenge query: \(O(\log N)\)

Algorithm

Each node of the segment tree stores the following values for its corresponding interval:

• sm: the sum of \(B_i\) values in the interval
• need: the minimum initial power required to clear the entire interval

For leaves, for room \(i\):

\[ \mathrm{sm} = B_i \]

\[ \mathrm{need} = A_i \]

For internal nodes, letting the left child be \(L\) and the right child be \(R\):

\[ \mathrm{sm} = \mathrm{sm}_L + \mathrm{sm}_R \]

\[ \mathrm{need} = \max(\mathrm{need}_L, \mathrm{need}_R - \mathrm{sm}_L) \]

Update Query

For 1 i a b, we update the information of room \(i\).

We change the corresponding leaf to:

\[ \mathrm{sm} = b \]

\[ \mathrm{need} = a \]

and recompute values upward toward the root.

This takes \(O(\log N)\) since it only traverses the height of the segment tree.

Challenge Query

For 2 s, we find how many monsters can be defeated with initial power \(s\).

First, the root’s need is “the minimum initial power required to clear everything.”

Therefore, if

\[ s \geq \mathrm{need}_{\text{root}} \]

then all monsters can be defeated, and the answer is \(N\).

Otherwise, the player will fail at some point.
We descend from the root of the segment tree to find the first room where failure occurs.

Let \(L\) be the left child of the current node.

• If the current power can clear the entire left interval, i.e.,

\[ \mathrm{power} \geq \mathrm{need}_L \]

then all monsters in the left interval can be defeated.
So we update the power as:

\[ \mathrm{power} \leftarrow \mathrm{power} + \mathrm{sm}_L \]

and move to the right child.

• Otherwise, the failing room is within the left interval, so we move to the left child.

We repeat this until we reach a leaf.

When we reach a leaf, that leaf is “the first room that cannot be cleared.”
If room numbers are 0-indexed, the index directly gives the number of monsters defeated.

For example, if the first room that cannot be cleared is room \(k\), the number defeated is \(k-1\).
Since the code uses 0-indexed positions, the answer is p - size.

Complexity

• Time complexity: \(O((N + Q)\log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

The number of leaves is rounded up to a power of \(2\).
For extra leaves that don’t correspond to actual rooms, we set:

• sm = 0
• need = -\infty

so that they don’t affect the search.

In the code, NEG = -10**30 is used.

Also, need values are merged using the following formula:

sm[p] = sm[left] + sm[right]
need[p] = max(need[left], need[right] - sm[left])

For challenge queries, we first check whether the entire sequence can be cleared:

if s >= need[1]:
    ans.append(str(N))

Only when it cannot be fully cleared do we descend the segment tree to find the first room that cannot be defeated:

while p < size:
    left = p * 2
    if power >= need[left]:
        power += sm[left]
        p = left + 1
    else:
        p = left

Here, by moving to the right if the left interval can be cleared and to the left otherwise, we can identify the first failing room in \(O(\log N)\).

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    Q = next(it)

    size = 1
    while size < N:
        size <<= 1

    NEG = -10**30
    sm = [0] * (size * 2)
    need = [NEG] * (size * 2)

    for i in range(N):
        a = next(it)
        b = next(it)
        p = size + i
        sm[p] = b
        need[p] = a

    for p in range(size - 1, 0, -1):
        l = p << 1
        r = l | 1
        sl = sm[l]
        sm[p] = sl + sm[r]
        x = need[r] - sl
        need[p] = need[l] if need[l] >= x else x

    ans = []

    for _ in range(Q):
        t = next(it)
        if t == 1:
            i = next(it) - 1
            a = next(it)
            b = next(it)

            p = size + i
            sm[p] = b
            need[p] = a
            p >>= 1

            while p:
                l = p << 1
                r = l | 1
                sl = sm[l]
                sm[p] = sl + sm[r]
                x = need[r] - sl
                need[p] = need[l] if need[l] >= x else x
                p >>= 1

        else:
            s = next(it)

            if s >= need[1]:
                ans.append(str(N))
                continue

            p = 1
            power = s
            while p < size:
                l = p << 1
                if power >= need[l]:
                    power += sm[l]
                    p = l | 1
                else:
                    p = l

            ans.append(str(p - size))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.