← 返回题目列表

AtCoder · abc427_g

G. 高桥的期待2

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


分数: 625 点

问题陈述

高桥从现在开始会收到一些礼物。

他有一个名为心情的整数参数,每次收到礼物时心情都会发生变化。 每个礼物都有一个称为值的整数参数 P,高桥的心情根据这个参数变化如下:

  • 如果该值 收到礼物的 P 大于等于心情值,他对礼物很满意,心情增加 A.
  • 如果该值 收到礼物的 P 收到的礼物小于心情值,他对礼物很失望,心情降低了 B.

最初,有 Vertex 上的 N 表示高桥计划收到,以及该值 i- 他将收到的第一份礼物 (1\le i\le N) is P _ i.

你被给予 Q 查询由两种类型组成:加法查询和问题查询。按顺序处理所有问题,并回答所有问题。

的 i-第一个查询由两个整数表示 T _ i,X _ i,如果 T _ i=1,以及一个问题查询 if T _ i=2.

在附加查询中,添加具有价值的新礼物 X _ i 到要收到的礼物结束。

在问题查询中,回答以下问题:

找出高桥在收到他预定收到的所有礼物后的心情,当时他的心情是 X _ i.

约束

  • 1\le N\le2\times10 ^ 5
  • 1\le A\le10 ^ 9
  • 1\le B\le10 ^ 9
  • -10 ^ 9\le P _ i\le10 ^ 9\ (1\le i\le N)
  • 1\le Q\le2\times10 ^ 5
  • T _ i=1 or T _ i=2\ (1\le i\le Q)
  • 存在一个整数 i\ (1\le i\le Q) 这样 T _ i=2.
  • If T _ i=1,那么 -10 ^ 9\le X _ i\le10 ^ 9. (1\le i\le Q)
  • If T _ i=2,那么 -10 ^ {12}\le X _ i\le10 ^ {12}. (1\le i\le Q)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N A B
P _ 1 P _ 2 \ldots P _ N
Q
T _ 1 X _ 1
T _ 2 X _ 2
\vdots
T _ Q X _ Q

输出

让 q 为问题查询数,并打印 q 行。 的 i第行 (1\le i\le q) 应包含以下问题的答案 i第问题查询。


示例输入 1

4 31 41
59 -26 53 58
5
2 9
1 79
2 32
1 38
2 462

示例输出 1

61
43
216

最初,高桥计划收到的礼物的价值是 59,-26,53,58,按照他收到的顺序。

五个查询如下:

  • 当他的心情最初是 9,他的情绪变化为 9\rightarrow40\rightarrow-1\rightarrow30\rightarrow61 每次他收到礼物,就打印最后的心情 61.
  • 有价值的礼物 79 被添加到他预定接收的礼物中,并且他预定接收的礼物的值变为 59,-26,53,58,79.
  • 当他的心情最初是 32,他的情绪变化为 32\rightarrow63\rightarrow22\rightarrow53\rightarrow84\rightarrow43 每次他收到礼物,就打印最后的心情 43.
  • 有价值的礼物 38 被添加到他预定接收的礼物中,并且他预定接收的礼物的值变为 59,-26,53,58,79,38.
  • 当他的心情最初是 462,他的情绪变化为 462\rightarrow421\rightarrow380\rightarrow339\rightarrow298\rightarrow257\rightarrow216 每次他收到礼物,就打印最后的心情 216.

示例输入 2

3 1000000000 1000000000
1000000000 0 -1000000000
3
2 -1000000000000
2 0
2 1000000000000

示例输出 2

-997000000000
-1000000000
997000000000

请注意,输入的绝对值和要输出的值可能是 2 ^ {32} 或更大。


示例输入 3

20 8489 1428
6312 -9511 1048 -5301 -2588 -7097 -3342 5209 7493 3378 -5300 6592 7862 -8118 8109 1116 5549 3953 9244 7773
10
1 1694
2 -9723
2 -5195
2 -1384
1 1149
2 9845
2 -7720
2 8329
2 -4652
2 -5672

示例输出 3

9874
14402
8296
8180
10449
6664
3600
12497