概要

区画ごとの水分量 \(C_i\) に対する「区間加算」と「閉鎖（削除）」が混ざる中で、ある区間内の「閉鎖されておらず \(C_i \le 0\)（乾燥）」な区画の収穫価値 \(S_i\) の総和を高速に求める問題です。

考察

重要な気づき

• 乾燥判定は「水分量が \(0\) 以下」つまり条件は \(C_i \le 0\) の しきい値判定です。
• 区間加算は同じ値 \(v\) を足すので、あるまとまり（ブロック）全体に加算できるなら 遅延加算（lazy）でまとめて持つと効率が良いです。
• さらに、ブロック内の（閉鎖されていない）要素を \(C\) の昇順に並べておけば、「\(C_i + \text{lazy} \le 0\)」を満たす要素数は二分探索で求まり、その分の \(S\) の総和も前計算の累積和で一気に求められます。

素朴解が厳しい理由

素朴に各クエリごとに区間を走査すると、操作3（問い合わせ）だけで \(O(N)\)、操作1（区間加算）も \(O(N)\) になり、全体で最悪 \(O(NQ)\) になります。制約が小さめとはいえ、より一般に通用する解法として「区間加算＋しきい値集計＋削除」をまとめて処理できる仕組みが必要です。

解決方針

• 配列を \(\sqrt{N}\) 程度のサイズのブロックに分ける（平方分割）。
• 各ブロックについて
  • ブロック全体に対する加算は lazy に貯める
  • “生存（alive）”の要素だけを取り出し、\((C,\ S)\) を \(C\) の昇順にソートして保持
  • ソート順に \(S\) の累積和 prefS を作る
• 問い合わせでブロックが丸ごと含まれる部分は二分探索で一瞬、端の部分ブロックだけは愚直に走査します。

アルゴリズム

1. 平方分割（ブロック分割）

インデックス \([0, N)\) をブロックサイズ \(B \approx \sqrt{N}\) で区切り、各ブロックは以下を持ちます。

• C[i]: lazy を含まない基準の水分量
• S[i]: 収穫価値
• alive[i]: 閉鎖されていないか
• lazy: ブロック全体に一様に足されている遅延加算
• sortedC: alive な要素の C を昇順に並べた配列
• prefS: sortedC と同順に並んだ \(S\) の累積和（prefS[k] は先頭から \(k\) 個の \(S\) の和）

2. ブロックの再構築 rebuild()

部分更新（端のブロックへの加算）や削除が起きると、ブロック内部の情報が壊れるので作り直します。

• alive な要素だけ集めて \((C_i, S_i)\) の配列を作る
• \(C_i\) でソート
• sortedC と prefS を作成

このとき C は lazy を含まない値のままです（lazy は別管理）。

3. 操作1：区間加算 1 l r v

区間 \([l, r)\) に \(v\) を加算します。

• 左端ブロック・右端ブロック（同じならその1ブロック）は、対象範囲の要素を直接 C[i] += v して rebuild()
• 間に完全に含まれるブロックは lazy += v するだけ（再構築不要）

※ すでに lazy があるブロックの一部だけを更新するときも、実値は \((C_i + lazy)\) なので
\((C_i + lazy) + v = (C_i + v) + lazy\)
となり、C[i] += v で正しく処理できます。

4. 操作2：削除 2 x

区画 \(x\) を閉鎖（alive を False）し、そのブロックを rebuild() します。

5. 操作3：問い合わせ 3 l r

区間 \([l, r)\) において「alive かつ \((C_i + lazy) \le 0\)」の \(S_i\) の総和。

• 端のブロックは愚直に走査して条件判定し加算
• 完全に含まれるブロックは一括で処理：
  • 条件 \((C_i + lazy) \le 0 \iff C_i \le -lazy\)
  • t = -lazy として k = bisect_right(sortedC, t)（\(t\) 以下の個数）
  • 答えは prefS[k]

例：あるブロックで lazy = 3 のとき、乾燥条件は
\(C_i + 3 \le 0 \iff C_i \le -3\)
なので、sortedC の中で \(-3\) 以下の範囲を二分探索で数え、その分の \(S\) を prefS から即座に得られます。

計算量

ブロックサイズを \(B \approx \sqrt{N}\) とします。

• 時間計算量:
  
  • rebuild()：\(O(B \log B)\)
    
  • 操作1（区間加算）: 端のブロックで \(O(B \log B)\)（再構築込み）＋ 中央ブロックは \(O(\#\text{blocks})\)
    
  • 操作2（削除）: \(O(B \log B)\)
    
  • 操作3（問い合わせ）: 端の走査 \(O(B)\) ＋ 中央ブロックは各 \(O(\log B)\)
    よって全体として概ね \(O\big(Q(\sqrt{N}\log N)\big)\) 程度で動作します。
• 空間計算量: \(O(N)\)（各要素をブロックに持ち、補助配列 sortedC, prefS も合計で \(O(N)\)）

実装のポイント

• C は lazy を含まない基準値として管理し、ブロック全体加算は lazy に持たせます（混ぜない）。

• prefS は先頭に \(0\) を入れて長さを 要素数+1 にすると、prefS[k] が「先頭 \(k\) 個の和」になり扱いやすいです。

• bisect_right(sortedC, t) を使うと「\(t\) 以下の個数」が取れます（乾燥条件は \(\le\) なので right）。

• 削除や部分更新後は 必ず rebuild() して、sortedC と prefS を最新化します。

  ソースコード

import sys
from bisect import bisect_right
import math

class Block:
    __slots__ = ("l", "r", "n", "S", "C", "alive", "lazy", "sortedC", "prefS")

    def __init__(self, l, r, S_all, C_all):
        self.l = l
        self.r = r
        self.n = r - l
        self.S = S_all[l:r]
        self.C = C_all[l:r]  # base values (lazy not included)
        self.alive = [True] * self.n
        self.lazy = 0
        self.sortedC = []
        self.prefS = [0]
        self.rebuild()

    def rebuild(self):
        arr = [(self.C[i], self.S[i]) for i in range(self.n) if self.alive[i]]
        arr.sort()
        self.sortedC = [c for c, _ in arr]
        pref = [0]
        s = 0
        for _, v in arr:
            s += v
            pref.append(s)
        self.prefS = pref

    def query_all(self):
        # sum S for alive with (C + lazy) <= 0  <=>  C <= -lazy
        t = -self.lazy
        k = bisect_right(self.sortedC, t)
        return self.prefS[k]


def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    Q = int(next(it))
    S = [int(next(it)) for _ in range(N)]
    C = [int(next(it)) for _ in range(N)]

    B = int(math.isqrt(N)) + 1
    blocks = []
    block_id = [0] * N
    for start in range(0, N, B):
        end = min(N, start + B)
        blk = Block(start, end, S, C)
        bid = len(blocks)
        blocks.append(blk)
        for i in range(start, end):
            block_id[i] = bid

    out = []

    for _ in range(Q):
        t = int(next(it))
        if t == 1:
            l = int(next(it)) - 1
            r = int(next(it))  # exclusive
            v = int(next(it))
            if l >= r:
                continue
            bl = block_id[l]
            br = block_id[r - 1]
            if bl == br:
                blk = blocks[bl]
                L = l - blk.l
                R = r - blk.l
                c = blk.C
                for i in range(L, R):
                    c[i] += v
                blk.rebuild()
            else:
                blk = blocks[bl]
                L = l - blk.l
                R = blk.r - blk.l
                c = blk.C
                for i in range(L, R):
                    c[i] += v
                blk.rebuild()

                for b in range(bl + 1, br):
                    blocks[b].lazy += v

                blk = blocks[br]
                L = 0
                R = r - blk.l
                c = blk.C
                for i in range(L, R):
                    c[i] += v
                blk.rebuild()

        elif t == 2:
            x = int(next(it)) - 1
            b = block_id[x]
            blk = blocks[b]
            idx = x - blk.l
            blk.alive[idx] = False
            blk.rebuild()

        else:  # t == 3
            l = int(next(it)) - 1
            r = int(next(it))  # exclusive
            if l >= r:
                out.append("0")
                continue
            bl = block_id[l]
            br = block_id[r - 1]
            ans = 0
            if bl == br:
                blk = blocks[bl]
                L = l - blk.l
                R = r - blk.l
                lazy = blk.lazy
                c = blk.C
                s = blk.S
                alive = blk.alive
                for i in range(L, R):
                    if alive[i] and c[i] + lazy <= 0:
                        ans += s[i]
            else:
                blk = blocks[bl]
                L = l - blk.l
                R = blk.r - blk.l
                lazy = blk.lazy
                c = blk.C
                s = blk.S
                alive = blk.alive
                for i in range(L, R):
                    if alive[i] and c[i] + lazy <= 0:
                        ans += s[i]

                for b in range(bl + 1, br):
                    ans += blocks[b].query_all()

                blk = blocks[br]
                L = 0
                R = r - blk.l
                lazy = blk.lazy
                c = blk.C
                s = blk.S
                alive = blk.alive
                for i in range(L, R):
                    if alive[i] and c[i] + lazy <= 0:
                        ans += s[i]

            out.append(str(ans))

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


if __name__ == "__main__":
    main()

---

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