#PQJ2470x15141. QOJ 2470_15141

    ID: 2827 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SCOI 2011并查集线段树平衡树

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 。