← 返回题目列表

AtCoder · awc0091_e

E. 家庭预算和目标余额

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

分数: 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 (R or L)和金额 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