← 返回题目列表

AtCoder · past201912_h

H. 批量销售

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

警告

在日本标准时间 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。 每个请求将按如下方式处理:

  1. 出售一张卡 2。你现在有 5,2,3,5 卡副本 1,2,3,4 有库存。
  2. 出售两张卡 1 和 3 每个。你现在有 3,2,1,5 有库存。
  3. 您没有足够的卡副本 3 有库存。什么也不做。
  4. 库存不足。什么也不做。
  5. 每种卡片出售一张。你现在有 2,1,0,4 有库存。
  6. 库存不足。什么也不做。

如上所示,我们将出售 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