概要

部屋の情報が更新される中で、「初期戦闘力 \(s\) で先頭から何体倒せるか」を高速に答える問題です。

各区間について「その区間をすべて突破するために必要な最小初期戦闘力」と「倒したときに得られる戦闘力の合計」をセグメント木で管理します。

考察

ある連続した部屋の区間について、次の \(2\) つの値を持つことを考えます。

• \(\mathrm{sum}\)：その区間のモンスターをすべて倒したときに増える戦闘力の合計
• \(\mathrm{need}\)：その区間のモンスターをすべて倒すために、区間に入る前に必要な最小戦闘力

例えば、部屋 \(i\) だけの区間なら、

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

です。

ここで、区間を左半分 \(L\)、右半分 \(R\) に分けて考えます。

左半分を突破するには、最初の戦闘力が \(\mathrm{need}_L\) 以上必要です。

また、左半分を突破した後、戦闘力は \(\mathrm{sum}_L\) 増えます。
右半分を突破するには、その時点で \(\mathrm{need}_R\) 以上必要なので、最初の戦闘力 \(x\) について

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

つまり、

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

が必要です。

したがって、左右を合わせた区間全体を突破するために必要な戦闘力は、

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

となります。

また、増える戦闘力の合計は単純に

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

です。

このように、区間の情報は左右の子区間の情報から計算できます。
よって、セグメント木で管理できます。

素朴に各クエリで部屋 \(1\) から順番にシミュレーションすると、種類 2 のクエリごとに \(O(N)\) かかります。
\(N, Q\) は最大で \(2 \times 10^5\) 程度なので、最悪 \(O(NQ)\) となり間に合いません。

そこで、セグメント木を使って、

• 更新クエリ：\(O(\log N)\)
• 挑戦クエリ：\(O(\log N)\)

で処理します。

アルゴリズム

セグメント木の各ノードに、対応する区間について次の値を持たせます。

• sm：その区間の \(B_i\) の合計
• need：その区間をすべて突破するために必要な最小戦闘力

葉では、部屋 \(i\) について

\[ \mathrm{sm} = B_i \]

\[ \mathrm{need} = A_i \]

とします。

内部ノードでは、左の子を \(L\)、右の子を \(R\) とすると、

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

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

で計算します。

更新クエリ

1 i a b の場合、部屋 \(i\) の情報を更新します。

対応する葉を

\[ \mathrm{sm} = b \]

\[ \mathrm{need} = a \]

に変更し、そこから根に向かって値を再計算します。

これはセグメント木の高さ分だけなので \(O(\log N)\) です。

挑戦クエリ

2 s の場合、初期戦闘力 \(s\) で何体倒せるかを求めます。

まず、根の need は「全体を突破するために必要な最小戦闘力」です。

したがって、

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

なら、すべてのモンスターを倒せるので答えは \(N\) です。

そうでない場合、どこかで倒せなくなります。
セグメント木を根から降りながら、最初に失敗する部屋を探します。

現在見ているノードの左の子を \(L\) とします。

• もし現在の戦闘力で左区間をすべて突破できる、つまり

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

なら、左区間のモンスターはすべて倒せます。
そのため、戦闘力を

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

として、右の子へ進みます。

• そうでなければ、失敗する部屋は左区間の中にあるので、左の子へ進みます。

これを葉に到達するまで繰り返します。

葉に到達したとき、その葉が「最初に倒せない部屋」です。
部屋番号を \(0\) 始まりで見ている場合、その添字がそのまま倒せたモンスター数になります。

例えば、最初に倒せない部屋が部屋 \(k\) なら、倒せた数は \(k-1\) です。
コードでは \(0\) 始まりの添字を使っているため、答えは p - size になります。

計算量

• 時間計算量: \(O((N + Q)\log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

葉の数は \(2\) のべき乗にそろえています。
実際には存在しない余分な葉については、探索に影響しないように

• sm = 0
• need = -\infty

としておきます。

コードでは NEG = -10**30 を使っています。

また、need の値は次の式でマージします。

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

挑戦クエリでは、まず全体を突破できるかを確認します。

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

突破できない場合だけ、セグメント木を降りて最初に倒せない部屋を探します。

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

このとき、左区間を突破できるなら右へ、できないなら左へ進むことで、最初に失敗する部屋を \(O(\log N)\) で特定できます。

ソースコード

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()

---

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