Skip to content

14103: 【原4103】Bang

题目

题目描述

author: Lmxyy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4103

Description

范细榜和金之榜是好朋友。他们住在一个盛产膀的国家,该国有\(N\)个城市,第\(i\)个城市的膀资源丰富度为\(W_i\)。并且该国交通十分发达,所有城市通过\(M\)条双向公路联通,并且从一个城市出发到达该国家的任何一个城市。

有时候他们两个会决定一起去买膀。范细榜从城市\(B\)出发,金之榜从城市\(C\)出发。他们每天可以且必须从一个城市移动到其相邻的城市。他们甚至可以到之前去过的城市。经过\(X\)天后(\(X\)为任意非负整数,且由两人自行决定),他们最终决定停留在那座城市买膀(两人最后可以在同一城市)。由于二人关系很好,所以为了顾及对方感情,他们觉得他们最后所停留的城市膀资源丰富度的差要尽可能小,否则可能一个会超巨膀,一个会变成超细膀。他们想知道,这个差最小是多少?

同时有时候,膀资源也会发生变动,在特定时候城市\(P\)的膀资源会变成\(Q\)。

Input Format

第一行三个整数\(N,M\),如题意。

第二行\(N\)个数\(W_1 \dots W_N\),表示这些城市的初始膀资源分布。

接下来\(M\)行,每行两个数\(a_i,b_i\),表示城市\(a_i\)与\(b_i\)毗邻。

再一行一个数字\(Q\),表示接下来会发生\(Q\)件事。

紧接着\(Q\)行,每行三个数\(A_i,B_i,C_i\)。

  • 若\(A_i = 0\),表示这时城市\(B_i\)的膀资源丰富度变为了\(C_i\)。

  • 若\(A_i = 1\),表示这时范细膀和金之榜决定外出买膀,一个从\(B_i\)城市出发,一个从\(C_i\)城市出发。

Output Format

对于每个\(A_i=1\)的操作,输出一行,包含一个最小差值。

Sample Input

6 6 
0 0 0 0 0 0 
1 2
1 6
5 1
2 3
3 4
3 5
7
1 1 2
0 1 10
0 3 20 
1 1 2
0 4 11 
1 1 3 
1 1 6

Sample Output

0
10 
0 
1

Data Range

对于\(10\%\)的数据,\(N \le 10,M \le 20,Q \le 10\)。

对于\(20\%\)的数据,\(N \le 100,M \le 200,Q \le 100\)。

对于\(30\%\)的数据,\(N \le 1000,M \le 2000,Q \le 1000\)。

对于\(40\%\)的数据,\(N \le 1000,M \le 200000,Q \le 1000\)。

对于另外\(10\%\)的数据,\(A_i=1\)。

对于\(100\%​\)的数据,\(N \le 100000\),\(M \le 200000\),\(Q \le 100000\),\(W_i,C_i \le 10^9\)。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!