/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 625 点
問題文
高橋くんは、これからいくつかのプレゼントをもらいます。
高橋くんにはテンションという整数のパラメータがあり、テンションはプレゼントをもらうごとに変動します。 それぞれのプレゼントは価値 P という整数のパラメータをもち、このパラメータによって高橋くんのテンションは次のように変動します。
- もらったプレゼントの価値 P がテンションの値以上であるとき、高橋くんはプレゼントに喜び、テンションが A だけ増加する。
- もらったプレゼントの価値 P がテンションの値より小さいとき、高橋くんはプレゼントにがっかりし、テンションが B だけ減少する。
はじめ、高橋くんが受け取る予定のプレゼントは N 個あり、i 番目 (1\le i\le N) に受け取るプレゼントの価値は P _ i です。
追加クエリ、質問クエリの 2 種類からなる Q 個のクエリが与えられるので、その全てを順に処理し、すべての質問クエリに答えてください。
i 番目のクエリは 2 つの整数 T _ i,X _ i によって表され、T _ i=1 のとき追加クエリ、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 もしくは T _ i=2\ (1\le i\le Q)
- T _ i=2 となるような整数 i\ (1\le i\le Q) が存在する
- T _ i=1 ならば -10 ^ 9\le X _ i\le10 ^ 9\ (1\le i\le Q)
- 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 です。
5 回のクエリは、それぞれ次のようになっています。
- 高橋くんのテンションがはじめ 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
Score : 625 points
Problem Statement
Takahashi will receive some presents from now on.
He has an integer parameter called mood, and the mood changes each time he receives a present. Each present has an integer parameter called value P, and Takahashi's mood changes according to this parameter as follows:
- If the value P of the received present is greater than or equal to the mood value, he is delighted with the present, and the mood increases by A.
- If the value P of the received present is less than the mood value, he is disappointed with the present, and the mood decreases by B.
Initially, there are N presents that Takahashi is scheduled to receive, and the value of the i-th present he will receive (1\le i\le N) is P _ i.
You are given Q queries consisting of two types: addition queries and question queries. Process all of them in order, and answer all question queries.
The i-th query is represented by two integers T _ i,X _ i, and it is an addition query if T _ i=1, and a question query if T _ i=2.
In an addition query, add a new present with value X _ i to the end of the presents to be received.
In a question query, answer the following question:
Find Takahashi's mood after receiving all the presents he is scheduled to receive when his mood is initially X _ i.
Constraints
- 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)
- There exists an integer i\ (1\le i\le Q) such that T _ i=2.
- If T _ i=1, then -10 ^ 9\le X _ i\le10 ^ 9. (1\le i\le Q)
- If T _ i=2, then -10 ^ {12}\le X _ i\le10 ^ {12}. (1\le i\le Q)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A B P _ 1 P _ 2 \ldots P _ N Q T _ 1 X _ 1 T _ 2 X _ 2 \vdots T _ Q X _ Q
Output
Let q be the number of question queries, and print q lines. The i-th line (1\le i\le q) should contain the answer to the i-th question query.
Sample Input 1
4 31 41 59 -26 53 58 5 2 9 1 79 2 32 1 38 2 462
Sample Output 1
61 43 216
Initially, the values of the presents Takahashi is scheduled to receive are 59,-26,53,58, in the order he will receive them.
The five queries are as follows:
- When his mood is initially 9, his mood changes as 9\rightarrow40\rightarrow-1\rightarrow30\rightarrow61 each time he receives a present, so print the final mood 61.
- A present with value 79 is added to the presents he is scheduled to receive, and the values of the presents he is scheduled to receive become 59,-26,53,58,79.
- When his mood is initially 32, his mood changes as 32\rightarrow63\rightarrow22\rightarrow53\rightarrow84\rightarrow43 each time he receives a present, so print the final mood 43.
- A present with value 38 is added to the presents he is scheduled to receive, and the values of the presents he is scheduled to receive become 59,-26,53,58,79,38.
- When his mood is initially 462, his mood changes as 462\rightarrow421\rightarrow380\rightarrow339\rightarrow298\rightarrow257\rightarrow216 each time he receives a present, so print the final mood 216.
Sample Input 2
3 1000000000 1000000000 1000000000 0 -1000000000 3 2 -1000000000000 2 0 2 1000000000000
Sample Output 2
-997000000000 -1000000000 997000000000
Note that the absolute value of the input and the values to be output may be 2 ^ {32} or greater.
Sample Input 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
Sample Output 3
9874 14402 8296 8180 10449 6664 3600 12497