← 返回题目列表

AtCoder · past17_o

O. 土地平整查询

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

问题陈述

给你一个整数序列 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