P15762 [JAG 2025 Summer Camp #1] Inside Yamanote

有 $N$ 个城市，编号从 $0$ 到 $N - 1$。一条铁路环绕所有 $N$ 个城市，城市 $i$ 和城市 $(i + 1) \bmod N$ 之间可以在 $L_i$ 个单位时间内通行。 你将实施以下政策： - 你可以修建任意数量的铁路，允许任意两个城市之间以任意非负时间通行。 - 然后，你从这 $N$ 个城市中选择一个作为首都。从首都到城市 $i$ 使用铁路所需的最短旅行时间，定义为该城市的欠发达指数 $d_i$。 该政策的声誉将由今年将要搬迁的 $M$ 位居民的口碑决定。居民 $j$ 将在政策实施后从城市 $X_j$ 搬迁到城市 $Y_j$。声誉将是所有 $d_{X_j} - d_{Y_j}$ 的总和。 你的目标是最大化该政策的声誉。然而，现有铁路的翻修工作也在进行中，你必须相应地调整政策。 现有铁路的旅行时间将发生 $Q$ 次变更。在第 $k$ 次变更中，城市 $T_k$ 和城市 $(T_k + 1) \bmod N$ 之间的旅行时间变为 $Z_k$。这些变更是永久性的。在每次变更后，输出在新条件下政策可能获得的最大声誉。

输入格式如下： $$\begin{aligned} & N \ M \ Q \\ & L_0 \ L_1 \ \ldots \ L_{N-1} \\ & X_1 \ Y_1 \\ & X_2 \ Y_2 \\ & \vdots \\ & X_M \ Y_M \\ & T_1 \ Z_1 \\ & T_2 \ Z_2 \\ & \vdots \\ & T_Q \ Z_Q \end{aligned}$$ - $3 \leq N \leq 200\,000$ - $1 \leq M \leq 200\,000$ - $1 \leq Q \leq 200\,000$ - $0 \leq L_i \leq 10^6$ ($1 \leq i \leq N$) - $0 \leq X_j, Y_j \leq N - 1$ ($1 \leq j \leq M$) - $X_j \neq Y_j$ ($1 \leq j \leq M$) - $0 \leq T_k \leq N - 1$ ($1 \leq k \leq Q$) - $0 \leq Z_k \leq 10^6$ ($1 \leq k \leq Q$) - 所有输入值均为整数。

输出 $Q$ 行。在第 $k$ 行（$1 \leq k \leq Q$），输出第 $k$ 个询问的答案。可以证明答案是整数。

翻译由 DeepSeek V3.2 完成