P13773 [CERC 2021] Single-track railway

在单轨铁路上行驶的列车只能在车站相遇。假设有一对列车同时从相反方向出发，一列从起始车站出发，另一列从终点车站（即反方向的起始车站）出发。很可能其中一列需要在某个车站等待另一列。为了最小化延误，列车应在某个车站相遇，使得等待时间最小。 我们已知每对相邻车站之间的行驶时间，且两个方向的行驶时间相同。不幸的是，由于铁路沿线施工，行驶时间会不断变化。你将获得初始的行驶时间，以及每次变更后受影响区段的最新行驶时间。请编写程序，在每次变更后，计算一对从铁路两端出发的列车可能的最短等待时间。

第一行给出车站数 $n$。第二行给出 $n-1$ 个数，分别表示相邻车站之间的初始行驶时间（第 $i$ 个数表示车站 $i$ 和 $i+1$ 之间的行驶时间）。第三行给出变更次数 $k$。接下来 $k$ 行，每行包含两个数：第一个数 $j \in [1, n-1]$，表示受影响的车站编号，第二个数为车站 $j$ 和 $j+1$ 之间的最新行驶时间。注意，车站编号从 1 开始。

输出 $k+1$ 行，第 $i$ 行表示第 $i-1$ 次变更后（第 1 行为未发生任何变更时）的最短等待时间。

### 说明 一开始，两列车应在第 3 号车站相遇。第一列车到达该站需 90 分钟，第二列车需 100 分钟，因此等待时间为 10 分钟。第一次变更后，最优相遇点变为第 4 号车站，两列车都需 130 分钟到达，因此无需等待。第二次变更后，仍在第 4 号车站相遇，但先到达的列车需等待 40 分钟。 ### 输入范围 - $2 \leq n \leq 200\,000$ - $0 \leq k \leq 200\,000$ - 所有行驶时间（初始和更新后）均为区间 $[1, 10^6]$ 内的整数。 由 ChatGPT 4.1 翻译