概要

この問題は、畑の各区画の水分量を更新し、閉鎖操作を行いながら、指定範囲内の乾燥状態にある区画の収穫価値の合計を求めるクエリを処理するものです。

考察

問題の制約条件（\(N, Q \leq 3000\)）を考えると、各操作を素直にシミュレーションする方法が有効です。操作1（区間加算）と操作3（区間合計）を愚直にループで処理しても、最悪ケースで\(3000 \times 3000 = 9 \times 10^6\)回の操作となり、現代的なコンピュータでは十分処理可能です。データ構造を工夫する必要はなく、シンプルな配列とフラグ管理で対応できます。

アルゴリズム

1. データの初期化: 収穫価値\(S_i\)と水分量\(C_i\)を配列で保持し、各区画の閉鎖状態を管理するブーリアン配列closedを準備します
2. クエリ処理:
   • 操作1 (1 l r v): \(l\)から\(r\)までの各区画について、閉鎖されていなければ水分量\(C_i\)に\(v\)を加算します
   • 操作2 (2 x): 区画\(x\)を閉鎖状態に設定します
   • 操作3 (3 l r): \(l\)から\(r\)までの各区画について、閉鎖されておらず、かつ水分量が\(0\)以下である区画の収穫価値\(S_i\)を合計します

計算量

• 時間計算量: \(O(N \cdot Q)\)（最悪ケースでは操作1と操作3が毎回全区間を処理する場合）
• 空間計算量: \(O(N)\)（各区画の情報を保持するための配列のみ使用）

実装のポイント

• 閉鎖状態を管理するclosed配列を用意し、操作2でフラグを立てる
• 操作1と操作3では、必ず閉鎖状態をチェックしてから処理を行う
• 入力データの読み込みにはsys.stdin.read()を使用し、イテレータで効率的に処理する
• 出力はリストに蓄積して最後に一括出力する（高速化のため）

このシンプルな実装は、制約条件内で十分効率的に動作します。より大きな制約の場合には遅延セグメント木などの高度なデータ構造が必要となりますが、本問題では必要ありません。

ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); Q = int(next(it))
    S = [0] * (N+1)
    C = [0] * (N+1)
    closed = [False] * (N+1)
    
    for i in range(1, N+1):
        S[i] = int(next(it))
    for i in range(1, N+1):
        C[i] = int(next(it))
    
    output_lines = []
    
    for _ in range(Q):
        op = next(it)
        if op == '1':
            l = int(next(it)); r = int(next(it)); v = int(next(it))
            for i in range(l, r+1):
                if not closed[i]:
                    C[i] += v
        elif op == '2':
            x = int(next(it))
            closed[x] = True
        elif op == '3':
            l = int(next(it)); r = int(next(it))
            total = 0
            for i in range(l, r+1):
                if not closed[i] and C[i] <= 0:
                    total += S[i]
            output_lines.append(str(total))
    
    print("\n".join(output_lines))

if __name__ == "__main__":
    main()

---

この解説は deepseekv3 によって生成されました。