A - 温度管理と収穫判定 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君は農園の管理者です。農園には N 区画の畑があり、それぞれに 1 から N までの番号が付けられています。

各区画 i（1 \leq i \leq N）には、その区画で育てている作物の「収穫価値」 S_i が定められています。収穫価値は操作によって変化しません。また、各区画 i には初期の土壌の「水分量」 C_i が与えられています。水分量は操作によって変化します。

ある時点において、水分量が 0 以下である区画を「乾燥状態」であるといいます。

高橋君は農園の天候や設備の状況に応じて Q 回の操作を順番に行います。各操作は次の 3 種類のいずれかです。

  • 操作 1：1 l r v — 番号 l から r までの区画のうち、閉鎖されていない各区画の水分量に v を加算する。v は負の値もあり得ます。これは降雨や日照りによる水分量の変動を表します。閉鎖された区画はこの操作の影響を受けません。
  • 操作 2：2 x — 区画 x を閉鎖する。閉鎖された区画は、以降のすべての操作および問い合わせにおいて存在しないものとして扱われます。具体的には、操作 1 による水分量の加算の対象にならず、操作 3 の集計対象にもなりません。一度閉鎖された区画が再び開放されることはありません。同じ区画に対して操作 2 が複数回行われることはないことが保証されます。
  • 操作 3：3 l r — 番号 l から r までの区画のうち、閉鎖されておらず、かつその時点で乾燥状態（水分量が 0 以下）であるすべての区画について、それらの収穫価値の合計を求め、出力します。該当する区画が存在しない場合は 0 を出力します。

すべての操作 3 に対して、現れた順に答えを出力してください。

制約

  • 1 \leq N \leq 3000
  • 1 \leq Q \leq 3000
  • 1 \leq S_i \leq 10^4（1 \leq i \leq N）
  • -10^4 \leq C_i \leq 10^4（1 \leq i \leq N）
  • 操作 1 において、1 \leq l \leq r \leq N、-10^4 \leq v \leq 10^4
  • 操作 2 において、1 \leq x \leq N
  • 操作 3 において、1 \leq l \leq r \leq N
  • 操作 2 で指定される区画 x は、その時点でまだ閉鎖されていない。同じ区画に対して操作 2 が複数回行われることはない
  • 入力はすべて整数である
  • 操作 3 は少なくとも 1 回与えられる

入力

N Q
S_1 S_2 \ldots S_N
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
  • 1 行目には、区画の数を表す整数 N と、操作の回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各区画の収穫価値を表す整数 S_1, S_2, \ldots, S_N がスペース区切りで与えられる。
  • 3 行目には、各区画の初期水分量を表す整数 C_1, C_2, \ldots, C_N がスペース区切りで与えられる。
  • 4 行目から Q 行にわたって、各操作が 1 行ずつ与えられる。各行の先頭の整数が操作の種類を表す。
  • 操作 1 の場合：1 l r v の 4 つの整数がスペース区切りで与えられる。l, r は対象範囲の左端・右端の区画番号、v は加算する水分量の変化値を表す。
  • 操作 2 の場合：2 x の 2 つの整数がスペース区切りで与えられる。x は閉鎖する区画の番号を表す。
  • 操作 3 の場合：3 l r の 3 つの整数がスペース区切りで与えられる。l, r は問い合わせ範囲の左端・右端の区画番号を表す。

出力

操作 3 が与えられるたびに、該当する範囲内で閉鎖されておらず、かつ乾燥状態（水分量が 0 以下）である区画の収穫価値の合計を 1 行に出力せよ。該当する区画が存在しない場合は 0 を出力せよ。操作 3 が複数回ある場合は、与えられた順にそれぞれの結果を出力せよ。

入力例 1

5 5
10 20 30 40 50
3 -1 0 5 -2
3 1 5
1 2 4 -5
3 1 5
2 3
3 1 5

出力例 1

100
140
110

入力例 2

8 8
5 15 25 35 10 20 30 40
1 -3 2 0 -1 4 -5 3
3 1 8
2 5
1 1 4 -2
3 1 6
1 6 8 -10
3 5 8
2 7
3 1 8

出力例 2

90
80
90
140

入力例 3

10 10
100 200 300 400 500 600 700 800 900 1000
5 -10 0 3 -7 8 1 -2 6 -4
3 1 10
1 1 5 -5
3 1 5
2 3
2 8
3 1 10
1 4 7 10
3 3 9
1 1 2 1
3 1 10

出力例 3

2800
1500
2200
500
1700

Score : 266 pts

Problem Statement

Takahashi is the manager of a farm. The farm has N plots of land, each numbered from 1 to N.

Each plot i (1 \leq i \leq N) has a designated "harvest value" S_i for the crop grown in that plot. The harvest value does not change through operations. Additionally, each plot i is given an initial soil "moisture level" C_i. The moisture level changes through operations.

At any given point in time, a plot whose moisture level is 0 or less is said to be in a "dry state".

Takahashi performs Q operations in order, depending on the weather and equipment conditions of the farm. Each operation is one of the following three types:

  • Operation 1: 1 l r v — For each non-closed plot numbered from l to r, add v to its moisture level. v can be negative. This represents changes in moisture due to rainfall or drought. Closed plots are not affected by this operation.
  • Operation 2: 2 x — Close plot x. A closed plot is treated as non-existent in all subsequent operations and queries. Specifically, it will not be subject to moisture addition in Operation 1, nor will it be included in the aggregation of Operation 3. Once a plot is closed, it is never reopened. It is guaranteed that Operation 2 is never performed more than once on the same plot.
  • Operation 3: 3 l r — Among the plots numbered from l to r that are not closed and are currently in a dry state (moisture level 0 or less), compute and output the sum of their harvest values. If no such plots exist, output 0.

For all Operation 3 queries, output the answers in the order they appear.

Constraints

  • 1 \leq N \leq 3000
  • 1 \leq Q \leq 3000
  • 1 \leq S_i \leq 10^4 (1 \leq i \leq N)
  • -10^4 \leq C_i \leq 10^4 (1 \leq i \leq N)
  • For Operation 1: 1 \leq l \leq r \leq N, -10^4 \leq v \leq 10^4
  • For Operation 2: 1 \leq x \leq N
  • For Operation 3: 1 \leq l \leq r \leq N
  • The plot x specified in Operation 2 has not yet been closed at that point. Operation 2 is never performed more than once on the same plot.
  • All input values are integers.
  • Operation 3 is given at least once.

Input

N Q
S_1 S_2 \ldots S_N
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
  • The first line contains two space-separated integers: N, the number of plots, and Q, the number of operations.
  • The second line contains N space-separated integers S_1, S_2, \ldots, S_N, representing the harvest value of each plot.
  • The third line contains N space-separated integers C_1, C_2, \ldots, C_N, representing the initial moisture level of each plot.
  • The following Q lines each describe one operation. The first integer on each line indicates the type of operation.
  • For Operation 1: Four space-separated integers 1 l r v are given. l and r are the left and right endpoints of the target range, and v is the moisture change value to add.
  • For Operation 2: Two space-separated integers 2 x are given. x is the number of the plot to close.
  • For Operation 3: Three space-separated integers 3 l r are given. l and r are the left and right endpoints of the query range.

Output

Each time Operation 3 is given, output on a single line the sum of harvest values of plots within the specified range that are not closed and are in a dry state (moisture level 0 or less). If no such plots exist, output 0. If Operation 3 occurs multiple times, output the results in the order they are given.

Sample Input 1

5 5
10 20 30 40 50
3 -1 0 5 -2
3 1 5
1 2 4 -5
3 1 5
2 3
3 1 5

Sample Output 1

100
140
110

Sample Input 2

8 8
5 15 25 35 10 20 30 40
1 -3 2 0 -1 4 -5 3
3 1 8
2 5
1 1 4 -2
3 1 6
1 6 8 -10
3 5 8
2 7
3 1 8

Sample Output 2

90
80
90
140

Sample Input 3

10 10
100 200 300 400 500 600 700 800 900 1000
5 -10 0 3 -7 8 1 -2 6 -4
3 1 10
1 1 5 -5
3 1 5
2 3
2 8
3 1 10
1 4 7 10
3 3 9
1 1 2 1
3 1 10

Sample Output 3

2800
1500
2200
500
1700