#PQJ2470x15141. QOJ 2470_15141
QOJ 2470_15141
有 𝑁 个节点,标号从 1 到 𝑁 ,这 𝑁 个节点一开始相互不连通。第 𝑖 个节点的初始权值为 𝑎 𝑖 ,接下来有如下一些操作:
U x y 加一条边,连接第 𝑥 个节点和第 𝑦 个节点。 A1 x v 将第 𝑥 个节点的权值增加 𝑣 。 A2 x v 将第 𝑥 个节点所在的连通块的所有节点的权值都增加 𝑣 。 A3 v 将所有节点的权值都增加 𝑣 。 F1 x 输出第 𝑥 个节点当前的权值。 F2 x 输出第 𝑥 个节点所在的连通块中,权值最大的节点的权值。 F3 输出所有节点中,权值最大的节点的权值。 输入格式
输入的第一行是一个整数 𝑁 ,代表节点个数。
接下来一行输入 𝑁 个整数, 𝑎 1 , 𝑎 2 , … , 𝑎 𝑁 ,代表 𝑁 个节点的初始权值。
再下一行输入一个整数 𝑄 ,代表接下来的操作数。
最后输入 𝑄 行,每行的格式如题目描述所示。
输出格式
对于操作 F1,F2,F3,输出对应的结果,每个结果占一行。
样例数据 样例 1 输入 3 0 0 0 8 A1 3 -20 A1 2 20 U 1 3 A2 1 10 F1 3 F2 3 A3 -10 F3 样例 1 输出 -10 10 10 子任务
对于 30 % 的数据,保证 𝑁 ≤ 100 , 𝑄 ≤ 10 4 。
对于 80 % 的数据,保证 𝑁 ≤ 10 5 , 𝑄 ≤ 10 5 。
对于 100 % 的数据,保证 𝑁 ≤ 3 × 10 5 , 𝑄 ≤ 3 × 10 5 。
对于所有的数据,保证输入合法,并且 − 10 3 ≤ 𝑣 , 𝑎 1 , 𝑎 2 , … , 𝑎 𝑁 ≤ 10 3 。