/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
問題文
長さ N の整数列 A = (A_1,A_2,\ldots,A_N) が与えられます。 この数列に対する操作を以下のように定めます。
- 操作：A の要素を 1 つ選んで、 1 または -1 を加算する。
クエリが Q 個与えられるので、与えられた順番に処理してください。クエリは次の 2 種類のいずれかです。
1 k d: A_k に d を加算する (d は 1 または -1)。2 x: A の要素を全て x にするために必要な操作回数の最小値を求める。ただし、実際には操作は行わない。
制約
- 入力は全て整数
- 1\leq N,Q \leq 2\times 10^5
- |A_i| \leq 10^9
- 1 番目の形式のクエリについて、1\leq k \leq N
- 1 番目の形式のクエリについて、d は 1 または -1
- 2 番目の形式のクエリについて、|x| \leq 10^9
- 2 番目の形式のクエリが少なくとも 1 つ与えられる
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
ただし、\mathrm{query}_i は i 個目のクエリを表しており、次の形式のいずれかで与えられる。
1 k d
2 x
出力
2 番目の形式のクエリの回数を q 回として、q 行出力せよ。 j\ (1\leq j \leq q) 行目には、2 番目の形式のクエリのうち j 個目のものに対する答えを出力せよ。
入力例 1
4 3 5 7 2 4 2 4 1 1 1 1 2 -1 2 4
出力例 1
7 5
最初、A = (3,5,7,2) です。
- 1 番目のクエリでは、A_1 に 1 を足す操作を 1 回、A_2 に -1 を足す操作を 1 回、 A_3 に -1 を足す操作を 3 回、A_4 に 1 を足す操作を 2 回行うのが最適です。よって、1+1+3+2=7 を出力します。
- 2 番目のクエリでは、A_1 に 1 が足されます。A=(4,5,7,2) になります。
- 3 番目のクエリでは、A_2 に -1 が足されます。A=(4,4,7,2) になります。
- 4 番目のクエリでは、A_3 に -1 を足す操作を 3 回、A_4 に 1 を足す操作を 2 回行うのが最適です。よって、3+2=5 を出力します。
入力例 2
10 403 -397 -538 -996 496 -499 80 768 714 -346 10 1 4 -1 2 -362 2 389 2 -470 1 2 -1 2 -58 1 5 1 1 10 1 2 -88 1 3 1
出力例 2
5270 5856 5632 5239 5239
Problem Statement
You are given an integer sequence A = (A_1,A_2,\ldots,A_N) of length N. We define an operation against this sequence as follows.
- Operation: choose an element of A, and add 1 or -1.
Given Q queries, process them in the given order. Each query is of one of the following two kinds.
1 k d: Add d to A_k (where d is 1 or -1).2 x: Find the minimum number of operations to make all the elements of A equal x. The operations are not actually performed.
Constraints
- All input values are integers.
- 1\leq N,Q \leq 2\times 10^5
- |A_i| \leq 10^9
- For each query of the 1-st kind, 1\leq k \leq N.
- For each query of the 1-st kind, d is 1 or -1.
- For each query of the 2-nd kind, |x| \leq 10^9.
- There is at least one query of the 2-nd kind.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Here, \mathrm{query}_i represents the i-th query, which is given in one of the following formats:
1 k d
2 x
Output
Print q lines, where q is the number of queries of the 2-nd kind. The j-th (1\leq j \leq q) line should contain the answer to the j-th query of the second kind.
Sample Input 1
4 3 5 7 2 4 2 4 1 1 1 1 2 -1 2 4
Sample Output 1
7 5
Initially, A = (3,5,7,2).
- For the 1-st query, it is optimal to add 1 to A_1 once, add -1 to A_2 once, add -1 to A_3 three times, and 1 to A_4 twice. Thus, 1+1+3+2=7 should be printed.
- For the 2-nd query, add 1 to A_1. Now, A=(4,5,7,2).
- For the 3-rd query, add -1 to A_2. Now, A=(4,4,7,2).
- For the 4-th query, it is optimal to add -1 to A_3 three times and 1 to A_4 twice. Thus, 3+2=5 should be printed.
Sample Input 2
10 403 -397 -538 -996 496 -499 80 768 714 -346 10 1 4 -1 2 -362 2 389 2 -470 1 2 -1 2 -58 1 5 1 1 10 1 2 -88 1 3 1
Sample Output 2
5270 5856 5632 5239 5239