分数: 266 分
问题陈述
高桥是一家农场的经理。农场有 N 地块,每块地编号为 1 to N.
每个情节 i (1 \leq i \leq N) 具有指定的“收获值” S_i 表示该地块中种植的作物。收获值不会因操作而改变。另外,每个地块 i 被赋予初始土壤“湿度水平” C_i。水分含量会随着操作而变化。
在任何给定的时间点,湿度水平为 0 或更少被认为处于“干燥状态”。
高桥表演 Q 作业是否有序,取决于农场的天气和设备状况。每个操作都是以下三种类型之一:
- 操作 1:
1 l r v- 对于每个非闭合图,编号为 l to r,添加 v 至其湿度水平。 v 可以为负数。这代表降雨或干旱导致的湿度变化。封闭的地块不受此操作的影响。 - 操作 2:
2 x— 关闭情节 x。在所有后续操作和查询中,封闭图将被视为不存在。具体来说,在操作中不会受到水分添加的影响。 1,也不会包含在Operation的聚合中 3。地块一旦关闭,就永远不会重新开放。保证运行 2 绝不会在同一地块上执行多次。 - 操作 3:
3 l r- 在编号为 l to 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
- 剧情 操作中指定的 x 操作中指定 2 此时尚未关闭。操作 2 绝不会在同一地块上执行多次。
- 所有输入值均为整数。
- 操作 3 至少给出一次。
输入
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
- 第一行包含两个空格分隔的整数: N,绘图数量,以及 Q,操作次数。
- 第二行包含 N 空格分隔的整数 S_1, S_2, \ldots, S_N,代表每个地块的收获值。
- 第三行包含 N 空格分隔的整数 C_1, C_2, \ldots, C_N,代表每个地块的初始湿度水平。
- 以下 Q 行每行描述一个操作。每行的第一个整数表示操作的类型。
- 操作 1:四个空格分隔的整数
给出了
1 l r v。 l 和 r 是目标范围的左端点和右端点,并且 v 是要添加的水分变化值。 - 操作 2:两个空格分隔的整数
2 x。 x 是要关闭的图的编号。 - 操作 3:三个空格分隔的整数
3 l r。 l 和 r 是查询范围的左端点和右端点。
输出
每次操作 给定 3 ,单行输出指定范围内未封闭且处于干燥状态(湿度水平)的地块收获值之和 0 或更少)。如果不存在这样的图,则输出 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