问题陈述
给你一个整数序列 A = (A_1,A_2,\ldots,A_N) 长度 N。 我们针对这个序列定义一个操作如下。
- 操作:选择一个元素 A,并添加 1 or -1.
鉴于 Q 查询,按给定顺序处理它们。每个查询都是以下两种类型之一。
1 k d:添加 d to A_k (其中 d is 1 or -1).2 x: 求使所有元素满足的最少操作次数 A 等于 x。这些操作并未实际执行。
约束
- 所有输入值均为整数。
- 1\leq N,Q \leq 2\times 10^5
- |A_i| \leq 10^9
- 对于每个查询 1-st 种, 1\leq k \leq N.
- 对于每个查询 1-st 种, d is 1 or -1.
- 对于每个查询 2-第一种, |x| \leq 10^9.
- 至少有一个查询 2-nd 种。
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \ldots A_N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
在这里, \mathrm{query}_i 代表 i-th 查询,以下列格式之一给出:
1 k d
2 x
输出
打印 q 行,其中 q 是查询的数量 2-第一种。 的 j-th (1\leq j \leq q) 行应包含以下问题的答案 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-st查询,最好添加 1 to A_1 一次,添加 -1 to A_2 一次, 添加 -1 to A_3 三次,并且 1 to A_4 两次。因此, 1+1+3+2=7 。
- 对于 2-nd查询,添加 1 to A_1。 现在, A=(4,5,7,2).
- 对于 3-rd查询,添加 -1 to A_2。 现在, A=(4,4,7,2).
- 对于 4-第一个查询,最好添加 -1 to A_3 三次并且 1 to A_4 两次。因此, 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