概要

\(N\) 個の区画の「収穫価値」と「水分量」を管理し、範囲への加算、区画の閉鎖、そして特定の条件（水分量が \(0\) 以下）を満たす区画の価値の合計を求める問題です。

考察

この問題の核心は、クエリごとに最大 \(N\) 個の区画を走査する必要がある点にあります。

• 制約の確認: \(N\) と \(Q\) はともに最大 \(3000\) です。単純なシミュレーションを行うと、計算量は最大で \(O(N \times Q)\) となり、操作回数は \(3000 \times 3000 = 9 \times 10^6\) 回程度になります。
• 計算量の見積もり: 一般的に、1秒間に処理できる計算量は \(10^7\) 〜 \(10^8\) 回程度と言われています。Pythonの場合、通常の for ループは低速ですが、リストのスライスや組み込み関数を適切に使うことで、この程度の計算量であれば制限時間内に処理することが可能です。
• 閉鎖された区画の扱い: 区画が閉鎖された場合、それ以降の計算から除外する必要があります。リストから要素を削除してしまうと、番号（インデックス）がずれてしまうため、「存在しないものとみなす」工夫が必要です。具体的には、収穫価値 \(S_i\) を \(0\) にし、水分量 \(C_i\) を絶対に \(0\) 以下にならないような大きな値に書き換えることで、条件判定と合計値の両方に影響を与えないようにできます。

アルゴリズム

各操作を愚直にシミュレーションする「計算幾何」や「セグメント木」などの高度なデータ構造を使わないアプローチをとります。

1. 初期化: 各区画の収穫価値 \(S\) と水分量 \(C\) を配列（リスト）で保持します。
2. 操作 1 (範囲加算): 指定された範囲 \([l, r]\) の \(C_i\) に対して \(v\) を加算します。Pythonではスライスを用いて C[l:r+1] = [c + v for c in C[l:r+1]] と書くことで高速に処理できます。
3. 操作 2 (区画閉鎖): 指定された区画 \(x\) を無効化します。
   • \(S_x = 0\) とする。
   • \(C_x = \infty\) （非常に大きな数）とする。
4. 操作 3 (条件付き合計): 範囲 \([l, r]\) を走査し、 \(C_i \leq 0\) である区画の \(S_i\) を合計します。

計算量

• 時間計算量: \(O(NQ)\)
  • 各クエリに対して最大 \(N\) 要素の走査や更新を行うため、全体の計算量は \(O(N \times Q)\) となります。\(N, Q \leq 3000\) では最大 \(9 \times 10^6\) であり、Pythonの高速な記法を用いることで十分に実行時間制限に間に合います。
• 空間計算量: \(O(N)\)
  • 区画の情報を保持するための配列のサイズは \(N\) に比例します。

実装のポイント

• 高速な入出力: \(Q\) が大きいため、input() を繰り返すのではなく sys.stdin.read().split() で一括で読み込み、sys.stdout.write で一括で出力することで実行時間を短縮しています。

• Pythonの高速化テクニック:

  • スライスとリスト内包表記: C[l:r+1] = [c + v for c in C[l:r+1]] は、通常の for ループで1要素ずつ更新するよりも内部的に最適化されており高速です。
  • zip関数の利用: 操作 3 で C と S の両方の値を参照する際、zip(sub_C, sub_S) を使うことでインデックスによるアクセス（sub_C[i]）を避け、より高速にループを回すことができます。

• 閉鎖の定数処理: 操作 2 で \(C_x\) に代入する値は、操作 1 で \(Q\) 回 \(10^4\) ずつ減らされたとしても \(0\) 以下にならないよう、\(10^9\) などの十分に大きな値にする必要があります。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを一括で読み込み、スペース区切りで分割します。
    # これにより、大量の入力データに対しても高速に処理を行うことができます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 区画の数, Q: 操作の回数
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # S: 各区画の収穫価値, C: 各区画の初期水分量
    S = [int(x) for x in input_data[2:N+2]]
    C = [int(x) for x in input_data[N+2:2*N+2]]
    
    # クエリ部分のデータを取得します。
    q_data = input_data[2*N+2:]
    results = []
    
    idx = 0
    # Q回の操作を順番に処理します。
    # Pythonのリスト操作（スライスやリスト内包表記）はC言語レベルで最適化されているため、
    # 5000x5000程度の計算量であれば時間内に処理が可能です。
    for _ in range(Q):
        if idx >= len(q_data):
            break
        
        t = q_data[idx]
        if t == '1':
            # 操作 1: 水分量の加算
            l = int(q_data[idx+1]) - 1
            r = int(q_data[idx+2]) - 1
            v = int(q_data[idx+3])
            if v != 0:
                # リスト内包表記を用いたスライスへの代入は、通常のforループより高速です。
                C[l:r+1] = [c + v for c in C[l:r+1]]
            idx += 4
        elif t == '2':
            # 操作 2: 区画の閉鎖
            x = int(q_data[idx+1]) - 1
            # 閉鎖された区画は、収穫価値を0にし、水分量を非常に大きな値に設定することで、
            # 以降の問い合わせにおいて条件を満たさない（かつ合計に影響を与えない）ようにします。
            S[x] = 0
            C[x] = 10**9 # 5000回の操作で減少しきらない十分大きな値
            idx += 2
        elif t == '3':
            # 操作 3: 収穫価値の合計
            l = int(q_data[idx+1]) - 1
            r = int(q_data[idx+2]) - 1
            
            total = 0
            # スライスとzipを組み合わせることで、インデックスによるアクセスを減らし、
            # ループの実行速度を向上させます。
            sub_C = C[l:r+1]
            sub_S = S[l:r+1]
            for ci, si in zip(sub_C, sub_S):
                if ci <= 0:
                    total += si
            results.append(str(total))
            idx += 3
    
    # すべての結果をまとめて出力します。
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。