题目描述
有 N 个城市，编号为 0,1,…,N−1。
一条铁路环绕所有 N 个城市。城市 i 和城市 (i+1)modN 之间可以在 Li 个单位时间内通行。
你将实施以下政策：
- 可以修建任意数量的铁路，并允许任意两个城市之间以任意非负时间通行。
- 从这 N 个城市中选择一个作为首都。从首都到城市 i 使用铁路所需的最短旅行时间，定义为该城市的欠发达指数 di。
该政策的声誉将由今年要搬迁的 M 位居民的口碑决定。居民 j 会在政策实施后从城市 Xj 搬迁到城市 Yj。政策的声誉为
j=1∑M(dXj−dYj).
你的目标是最大化该政策的声誉。
现有铁路正在翻修，因此你必须不断调整政策。现有铁路的旅行时间将发生 Q 次变更。在第 k 次变更中，城市 Tk 和城市 (Tk+1)modN 之间的旅行时间变为 Zk。这些变更是永久性的。
每次变更后，输出在当前条件下该政策可能获得的最大声誉。
输入格式
输入格式如下：
N M Q
L_0 L_1 ... L_{N-1}
X_1 Y_1
X_2 Y_2
...
X_M Y_M
T_1 Z_1
T_2 Z_2
...
T_Q Z_Q
输入满足：
- 3≤N≤200000；
- 1≤M≤200000；
- 1≤Q≤200000；
- 0≤Li≤106，其中 0≤i≤N−1；
- 0≤Xj,Yj≤N−1，其中 1≤j≤M；
- Xj=Yj，其中 1≤j≤M；
- 0≤Tk≤N−1，其中 1≤k≤Q；
- 0≤Zk≤106，其中 1≤k≤Q；
- 所有输入值均为整数。
输出格式
输出到文件 road.out 中。
输出 Q 行。第 k 行输出第 k 次变更后的答案。可以证明答案一定是整数。
样例 1
5 3 4
1 5 2 1 3
0 2
1 3
4 2
4 0
1 3
4 2
3 9
8
7
8
15
数据范围
对于所有数据：
1≤n,m,q≤2×105.
| 子任务编号 |
n≤ |
m≤ |
q≤ |
特殊限制 |
分值 |
| 1 |
5 |
2×105 |
5 |
无 |
20 |
| 2 |
2×105 |
1 |
2×105 |
| 3 |
2×105 |
1 |
| 4 |
2×105 |
A |
| 5 |
2×103 |
无 |
10 |
| 6 |
2×105 |
特殊性质 A：保证所有初始边权和修改后的边权均为 1，即 Li=1、Zi=1。
