← 返回题目列表

Codeforces · 295/E

E. 雅罗斯拉夫和点

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

Yaroslav 有 n 个点位于 Ox 轴上。第一个点的坐标是x1,第二个点的坐标是x2,...,第n个点的坐标是—xn。现在Yaroslav想要执行m个查询,每个查询都是以下两种类型之一:

1. 将第 pj 个点从位置 xpj 移动到位置 xpj + dj。这样,可以保证执行此类查询后,所有点的坐标都是不同的。
2. 计算线段 [lj, rj] 上所有点对之间的距离总和 (lj ≤ rj)。换句话说,您应该计算以下总和:$$\sum_{l_j \leq x_p \leq x_q \leq r_j} (x_q - x_p)$$。

帮助雅罗斯拉夫。

输入

第一行包含整数 n — 点数 (1 ≤ n ≤ 105)。第二行包含不同的整数 x1, x2, ..., xn — 点的坐标 (|xi| ≤ 109)。

第三行包含整数 m — 查询数量 (1 ≤ m ≤ 105)。接下来的 m 行包含查询。第 j 行首先包含整数 tj (1 ≤ tj ≤ 2) — 查询类型。如果 tj = 1,则后面跟着两个整数 pj 和 dj (1 ≤ pj ≤ n,|dj| ≤ 1000)。如果 tj = 2,则后面跟着两个整数 lj 和 rj (- 109 ≤ lj ≤ rj ≤ 109)。

保证在任何时刻所有点都有不同的坐标。

输出

对于每个类型 2 查询,将答案打印在一行上。按顺序打印答案,其中查询紧随输入。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 %I64d 说明符的 cin、cout 流。

示例

输入 #1

8
36 50 28 -75 40 -60 -95 -48
20
2 -61 29
1 5 -53
1 1 429
1 5 130
2 -101 -71
2 -69 53
1 1 404
1 5 518
2 -101 53
2 50 872
1 1 -207
2 -99 -40
1 7 -389
1 6 -171
1 2 464
1 7 -707
1 1 -730
1 1 560
2 635 644
1 7 -677

输出 #1

176
20
406
1046
1638
156
0