← 返回题目列表

Codeforces · 1814/E

E. 链片

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

给定一个由 $$$n$$$ 个顶点和 $$$n-1$$$ 边组成的无向图。第 $$$i$$$ 条边的权重为 $$$a_i$$$;它连接顶点 $$$i$$$ 和 $$$i+1$$$。

最初,每个顶点都包含一个芯片。每个芯片上都写有一个整数;写在芯片上第 $$$i$$$ 个顶点的整数是 $$$i$$$。

在一次操作中,您可以选择一个芯片(如果单个顶点中有多个芯片,您可以选择其中任何一个)并将其沿图的一条边移动。该操作的成本等于边的权重。

图的成本是满足以下条件的一系列此类操作的最小成本:

- 执行完所有操作后,每个顶点恰好包含一个筹码,并且每个筹码上的整数不等于该筹码所在顶点的索引。

您将收到以下形式的 $$$q$$$ 查询:

- $$$k$$$ $$$x$$$ — 将第 $$$k$$$ 条边(连接顶点 $$$k$$$ 和 $$$k+1$$$ 的边)的权重更改为 $$$x$$$。

每次查询后,打印图表的成本。请注意,您实际上并没有移动任何筹码;而是移动了任何筹码。当你计算成本时,筹码处于其初始位置。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n-1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$)。

第三行包含一个整数$$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$)。

然后是 $$$q$$$ 行。其中第 $$$i$$$ 包含第 $$$i$$$ 查询的两个整数 $$$k$$$ 和 $$$x$$$ ($$$1 \le k \le n-1$$$; $$$1 \le x \le 10^9$$$)。

输出

对于每个查询,打印一个整数 - 执行查询后图表的成本。

示例

输入 #1

10
12 6 12 15 20 8 17 12 15
8
4 10
7 3
6 14
9 9
2 10
3 5
4 11
7 11

输出 #1

126
108
120
108
112
98
98
114