警告
在日本标准时间 2019 年 12 月 29 日凌晨 05:00 之前请勿提及此问题。如有违反,可要求赔偿。
考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。
问题陈述
您将出售交易卡。 你有 N 各种卡片、卡片 1, \ldots, N,你有 C_i 卡副本 i (1 \leq i \leq N) 最初有库存。
现在,您必须处理 Q 请求 S_1, \ldots, S_Q 按顺序。每个请求均采用以下形式之一:
- 单一种类:出售 a 卡副本 x,或者如果您没有足够的库存副本,则不执行任何操作。以格式给出
1 x a. - 多种:出售 a 卡副本 x 对于每个奇数 x 之间 1 和 N (含),或者如果您没有足够的库存中的一种或多种此类副本,则不执行任何操作。以格式给出
2 a. - 所有种类:出售 a 卡副本 x 对于每个数字 x 之间 1 和 N,或者如果您没有足够的库存中的一种或多种此类副本,则不执行任何操作。以格式给出
3 a.
打印这些请求中将出售的卡片总数。
约束
- 1 \leq N \leq 200000
- 1 \leq C_i \leq 10^9
- 1 \leq Q \leq 200000
- S_i 是采用以下格式之一的字符串:
1 x a(1 \leq x \leq N 和 1 \leq a \leq 10^9)2 a(1 \leq a \leq 10^9)3 a(1 \leq a \leq 10^9)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N C_1 C_2 ... C_N Q S_1 S_2 : S_Q
输出
打印销售卡的总数 Q 请求。
样本输入 1
4 5 3 3 5 6 1 2 1 2 2 2 2 3 100 3 1 1 1 3
示例输出 1
9
最初,您有 分别是 5,3,3,5 卡副本 1,2,3,4。 每个请求将按如下方式处理:
- 出售一张卡 2。你现在有 5,2,3,5 卡副本 1,2,3,4 有库存。
- 出售两张卡 1 和 3 每个。你现在有 3,2,1,5 有库存。
- 您没有足够的卡副本 3 有库存。什么也不做。
- 库存不足。什么也不做。
- 每种卡片出售一张。你现在有 2,1,0,4 有库存。
- 库存不足。什么也不做。
如上所示,我们将出售 1, 4, 4 第一个、第二个、第五个请求中的卡片,总共 9 卡。
示例输入 2
10 241 310 105 738 405 490 158 92 68 20 20 2 252 1 4 36 2 69 1 5 406 3 252 1 3 8 1 10 10 3 11 1 4 703 3 1 2 350 3 10 2 62 2 3 2 274 1 2 1 3 126 1 4 702 3 6 2 174
示例输出 2
390
示例输入 3
2 3 4 3 1 2 9 2 4 3 4
示例输出 3
0