← 返回题目列表

AtCoder · awc0092_a

A. 水资源管理和收获价值汇总

中文机器翻译题面 查看原题

分数: 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