分数: 466 分
问题陈述
高桥管理着一本家庭预算簿,其中 N 交易按顺序记录。的 i- 第笔交易有一个类型 D_i 和金额 B_i.
- 如果类型是
R,该金额添加到余额(存款)中。 - 如果类型是
L,从余额中减去该金额(提款)。
高桥进程 Q 按照给出的顺序进行操作。有 2 操作类型:
1 p D b:修改 p- 第一个具有类型的交易 D 和金额 b.2 K:对于预算账簿的当前状态,从余额开始 0 并处理来自 1-st 以后,回答第一笔交易的数量,之后余额至少变为 K。如果余额永远达不到 K 或更多交易后,回答 0.
这里, i- 第笔交易是 i。处理过程中余额可能会变为负值。
类型 2 操作属于查询,不会改变预算书的内容。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 让 M 是类型的数量 所有操作中的 2 操作。然后 1 \leq M 和 N+Q+M \leq 2 \times 10^5.
- D_i \in \{\texttt{R}, \texttt{L}\}
- 1 \leq B_i \leq 10^9
- B_i 是一个整数
- 对于类型 1 操作:
- 1 \leq p \leq N
- D \in \{\texttt{R}, \texttt{L}\}
- 1 \leq b \leq 10^9
- b 是一个整数
- 对于类型 2 操作:
- 1 \leq K \leq 2 \times 10^{14}
- K 是一个整数
输入
N Q
D_1 B_1
D_2 B_2
:
D_N B_N
\mathrm{Query}_1
\mathrm{Query}_2
:
\mathrm{Query}_Q
- 第一行包含交易数量 N 和操作次数 Q,用空格分隔。
- 在下面 N 行, i第行包含类型 D_i 和金额 B_i 的 i- 第一个事务,以空格分隔。
- 以下 Q 行每行包含以下格式之一的操作:
1 p D b
2 K
1 p D b表示修改 p要输入的第笔交易 D (RorL)和金额 b.2 K表示查询目标余额 K.
输出
对于每种类型 2 运算,在一行中输出答案。
示例输入 1
5 6 R 10 L 3 R 5 L 20 R 15 2 7 2 12 1 4 L 4 2 12 1 2 R 2 2 20
示例输出 1
1 3 3 5
示例输入 2
3 4 L 10 R 5 L 1 2 1 2 100 1 2 L 5 2 1
示例输出 2
0 0 0
示例输入 3
10 12 R 8 L 4 R 15 L 10 R 7 R 3 L 20 R 25 L 5 R 6 2 10 2 20 1 7 L 5 2 30 1 4 R 12 2 40 1 1 L 3 2 5 2 50 1 10 L 2 2 25 2 60
示例输出 3
3 8 8 6 3 8 5 0
示例输入 4
30 30 R 100 L 40 R 70 L 150 R 200 L 30 L 80 R 300 L 120 R 50 R 400 L 500 R 600 L 100 R 90 L 250 R 700 L 60 R 30 L 20 R 1000 L 800 R 450 L 300 R 200 L 100 R 50 L 400 R 900 L 700 2 100 2 500 1 4 R 150 2 500 1 12 L 100 2 1000 1 22 R 800 2 2000 1 28 R 400 2 2500 1 1 L 100 2 50 2 3000 1 17 L 700 2 1500 1 30 R 700 2 3500 1 7 R 80 2 1200 1 21 L 1000 2 1000 1 5 L 200 2 800 1 13 L 600 2 700 1 2 R 40 2 600 1 29 L 900 2 400 2 5000
示例输出 4
1 11 8 11 21 21 4 22 22 29 13 13 13 30 11 11 0
示例输入 5
1 1 R 1000000000 2 200000000000000
示例输出 5
0