小C正在出一道题...因为语文水平有限他想不出复杂的背景,所以以下就是题意了。 平面上有N个点,开始时每个点属于一个不同的集合。不妨设点Pi属于集合Si。请维护数据结构支持以下三种操作: "Merge x y":将集合Sy中的点到Sx中; "Split i d v"(d?∈?{0,?1}):创建新集合Sc?+?1,Sc?+?2,之后将集合Si中的所有点中,第d维坐标不超过v的到集合Sc?+?1中,超过v的移动到集合Sc?+?2中,其中c为现有集合数( 包括之前合并和分割中产生的空集 ); "Query i":查询集合Si中点权值的最大值,最小值及和; "Add i d":将集合Si中所有点的权值增加d。 方便起见,对于d?∈?{0,?1},输入的所有点的第d维坐标不重复。所有操作涉及的集合非空。
第一行一个整数N表示点数。 接下来N行,每行3个整数分别表示Pi的坐标与权值。 接下来一个整数Q表示操作数。 接下来Q行,每行描述一个操作,格式如上所述。
对于每个Q操作,输出三个整数,依次表示询问集合权值的最大值,最小值与和。
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
N<=50000
Q<=100000