CF1814E Chain Chips

给定一个无向图，包含 $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$ 行，每行包含两个整数 $k$ 和 $x$（$1 \le k \le n-1$；$1 \le x \le 10^9$），表示第 $i$ 个询问。

对于每个询问，输出一个整数，表示该询问操作后图的总代价。

由 ChatGPT 4.1 翻译