概要

\(N\) 区画の畑に対して、「範囲の水分量加算」「区画の閉鎖」「範囲内で乾燥状態の区画の収穫価値合計を求める」の3種類の操作を処理する問題です。制約が小さいため、愚直なシミュレーションで解くことができます。

考察

まず制約を確認しましょう。

• \(N \leq 3000\)
• \(Q \leq 3000\)

各操作で最悪 \(N\) 個の区画を走査する必要がありますが、\(N \times Q \leq 3000 \times 3000 = 9 \times 10^6\) 程度なので、素朴に1つずつ処理しても十分間に合います。

セグメント木や遅延伝播などの高度なデータ構造は不要で、配列を直接操作するだけで解けます。

各操作の処理方針

• 操作1（範囲加算）: 区間 \([l, r]\) の各区画を順に見て、閉鎖されていなければ水分量に \(v\) を加算します。
• 操作2（閉鎖）: 区画 \(x\) に「閉鎖済み」フラグを立てます。以降の操作ではこの区画をスキップします。
• 操作3（乾燥区画の収穫価値合計）: 区間 \([l, r]\) の各区画を順に見て、「閉鎖されていない」かつ「水分量 \(C_i \leq 0\)（乾燥状態）」であれば収穫価値 \(S_i\) を合計に加えます。

例えば、\(S = [10, 20, 30]\)、\(C = [5, -3, 0]\) のとき、操作 3 1 3 が来ると： - 区画1: \(C_1 = 5 > 0\) → 対象外 - 区画2: \(C_2 = -3 \leq 0\) → 対象（\(+20\)） - 区画3: \(C_3 = 0 \leq 0\) → 対象（\(+30\)） - 答えは \(50\)

アルゴリズム

1. 配列 \(S\)（収穫価値）、\(C\)（水分量）、\(\text{closed}\)（閉鎖フラグ）を用意する。
2. \(Q\) 回の操作を順に処理する：
   • 操作1: \(l\) から \(r\) までループし、閉鎖されていない区画の \(C_i\) に \(v\) を加算。
   • 操作2: \(\text{closed}[x] = \text{True}\) に設定。
   • 操作3: \(l\) から \(r\) までループし、閉鎖されておらず \(C_i \leq 0\) の区画について \(S_i\) を合計して出力。

特別なデータ構造は使わず、配列の直接操作のみで実現しています。

計算量

• 時間計算量: \(O(N \times Q)\)
  • 操作1と操作3はそれぞれ最悪 \(O(N)\)、操作2は \(O(1)\)。全体で \(Q\) 回の操作があるため \(O(NQ)\)。\(N, Q \leq 3000\) より最大約 \(9 \times 10^6\) 回の処理で十分高速です。
• 空間計算量: \(O(N)\)
  • 配列 \(S\), \(C\), \(\text{closed}\) をそれぞれ \(N\) 要素分保持します。

実装のポイント

• 1-indexed と 0-indexed の変換: 問題文では区画番号が \(1\) から始まりますが、Python の配列は \(0\) から始まるため、range(l-1, r) のようにインデックスを調整します。

• 閉鎖された区画のスキップ: 操作1でも閉鎖された区画には水分量を加算しません。問題文に「閉鎖された区画は以降のすべての操作において存在しないものとして扱う」と明記されているためです。

• 出力の効率化: 操作3の結果を都度 print するのではなく、リストに溜めて最後に一括出力することで、I/O のオーバーヘッドを削減しています。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    S = list(map(int, input().split()))
    C = list(map(int, input().split()))
    closed = [False] * N
    
    results = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        op = line[0]
        if op == 1:
            l, r, v = line[1], line[2], line[3]
            for i in range(l - 1, r):
                if not closed[i]:
                    C[i] += v
        elif op == 2:
            x = line[1]
            closed[x - 1] = True
        else:
            l, r = line[1], line[2]
            total = 0
            for i in range(l - 1, r):
                if not closed[i] and C[i] <= 0:
                    total += S[i]
            results.append(total)
    
    print('\n'.join(map(str, results)))

main()

この解説は claude4.6opus-thinking によって生成されました。