310317: CF1814E. Chain Chips

Memory Limit:512 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Chain Chipstime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are given an undirected graph consisting of $n$ vertices and $n-1$ edges. The $i$-th edge has weight $a_i$; it connects the vertices $i$ and $i+1$.

Initially, each vertex contains a chip. Each chip has an integer written on it; the integer written on the chip in the $i$-th vertex is $i$.

In one operation, you can choose a chip (if there are multiple chips in a single vertex, you may choose any one of them) and move it along one of the edges of the graph. The cost of this operation is equal to the weight of the edge.

The cost of the graph is the minimum cost of a sequence of such operations that meets the following condition:

  • after all operations are performed, each vertex contains exactly one chip, and the integer on each chip is not equal to the index of the vertex where that chip is located.

You are given $q$ queries of the form:

  • $k$ $x$ — change the weight of the $k$-th edge (the one which connects the vertices $k$ and $k+1$) to $x$.

After each query, print the cost of the graph. Note that you don't actually move any chips; when you compute the cost, the chips are on their initial positions.

Input

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$).

The second line contains $n-1$ integers $a_1, a_2, \dots, a_{n-1}$ ($1 \le a_i \le 10^9$).

The third line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$).

Then $q$ lines follow. The $i$-th of them contains two integers $k$ and $x$ ($1 \le k \le n-1$; $1 \le x \le 10^9$) for the $i$-th query.

Output

For each query, print one integer — the cost of the graph after the query is performed.

ExampleInput
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
Output
126
108
120
108
112
98
98
114

Input

题意翻译

在一条长度为 $n$ 的链上,有 $1\sim n$ 这 $n$ 个点,第 $i$ 条边连接着第 $i$ 个点到第 $i+1$ 个点,长度是 $w_i$ 。 在一开始,在第 $i$ 个点上都停着一辆车 $i$ 。现在,你需要通过这些道路,移动一些车辆,使得每一辆车都不停在它的初始位置上,同时每个位置最终也**仅有一辆车**,并且车的移动总距离尽可能小。 接下来会有 $m$ 组询问,每组询问会修改一条边的边权,你需要输出修改后的车的移动的最小距离。修改不独立,车并不会真的移动。 $n,m\leq 2\times 10^5$

Output

题目大意:
给定一个包含n个顶点和n-1条边的无向图。第i条边的权重为a_i,连接顶点i和i+1。最初,每个顶点都有一块筹码,每块筹码上写有一个整数,第i个顶点上的筹码上的整数是i。每次操作可以选择一个筹码(如果单个顶点中有多个筹码,可以选择其中任何一个)并将其沿着图的一条边移动,此操作的成本等于边的权重。图的成本是最小操作序列的成本,满足条件:所有操作完成后,每个顶点恰好有一个筹码,且每块筹码上的整数不等于该筹码所在顶点的索引。给定q个查询,形式为:k x ——将第k条边(连接顶点k和k+1的边)的权重改为x。每次查询后,输出图的成本。注意,实际上并不移动任何筹码;在计算成本时,筹码位于它们的初始位置。

输入数据格式:
第一行包含一个整数n(2≤n≤2×10^5)。
第二行包含n-1个整数a_1, a_2, …, a_{n-1}(1≤a_i≤10^9)。
第三行包含一个整数q(1≤q≤2×10^5)。
然后是q行,每行包含两个整数k和x(1≤k≤n-1;1≤x≤10^9),代表第i个查询。

输出数据格式:
对于每个查询,输出一个整数——执行查询后图的成本。题目大意: 给定一个包含n个顶点和n-1条边的无向图。第i条边的权重为a_i,连接顶点i和i+1。最初,每个顶点都有一块筹码,每块筹码上写有一个整数,第i个顶点上的筹码上的整数是i。每次操作可以选择一个筹码(如果单个顶点中有多个筹码,可以选择其中任何一个)并将其沿着图的一条边移动,此操作的成本等于边的权重。图的成本是最小操作序列的成本,满足条件:所有操作完成后,每个顶点恰好有一个筹码,且每块筹码上的整数不等于该筹码所在顶点的索引。给定q个查询,形式为:k x ——将第k条边(连接顶点k和k+1的边)的权重改为x。每次查询后,输出图的成本。注意,实际上并不移动任何筹码;在计算成本时,筹码位于它们的初始位置。 输入数据格式: 第一行包含一个整数n(2≤n≤2×10^5)。 第二行包含n-1个整数a_1, a_2, …, a_{n-1}(1≤a_i≤10^9)。 第三行包含一个整数q(1≤q≤2×10^5)。 然后是q行,每行包含两个整数k和x(1≤k≤n-1;1≤x≤10^9),代表第i个查询。 输出数据格式: 对于每个查询,输出一个整数——执行查询后图的成本。

加入题单

上一题 下一题 算法标签: