#P3615. MSS
MSS
MSS
题目描述
小 C 要维护平面上的 个点。第 个点 有两个坐标和一个权值,初始时它单独属于编号为 的集合 。
需要按顺序处理四种操作。
Merge x y把集合 中的点移到集合 。Split i d v创建两个新的集合 。这里 是此前分配过的集合编号总数,包括已经变为空集的集合。把 中第 维坐标不超过 的点移入 ,其余点移入 。 表示横坐标, 表示纵坐标。Query i询问集合 内点权的最大值、最小值和总和。Add i d将集合 内所有点的权值增加 。
合并、分割和增加权值均不改变点的坐标。全部点的横坐标两两不同,纵坐标也两两不同。作为操作对象的集合保证非空。
输入格式
第一行一个整数 。接下来 行,每行三个整数,依次为该点的横坐标、纵坐标和初始权值。
接下来一行一个整数 ,表示操作数。随后 行各给出一个操作,格式见题目描述。
输出格式
每遇到一次 Query,就输出一行三个整数,分别表示该集合内点权的最大值、最小值和总和。
样例
5
4 7 3
18 16 2
14 13 1
10 2 10
3 8 5
11
Merge 2 3
Merge 4 5
Split 2 1 13
Query 4
Query 6
Add 6 2
Query 6
Merge 6 4
Split 6 0 10
Query 9
Split 8 0 3
10 5 15
1 1 1
3 3 3
3 3 3
数据范围
,。