题目描述

小C正在出一道题...因为语文水平有限他想不出复杂的背景，所以以下就是题意了。 平面上有N个点，开始时每个点属于一个不同的集合。不妨设点P_{i}属于集合S_{i}。请维护数据结构支持以下三种操作： "Merge x y"：将集合S_{y}中的点到S_{x}中； "Split i d v"（d ∈ {0, 1}）：创建新集合S_{c + 1}，S_{c + 2}，之后将集合S_{i}中的所有点中，第d维坐标不超过v的到集合S_{c + 1}中，超过v的移动到集合S_{c + 2}中，其中c为现有集合数（ 包括之前合并和分割中产生的空集 ）； "Query i"：查询集合S_{i}中点权值的最大值，最小值及和； "Add i d"：将集合S_{i}中所有点的权值增加d。 方便起见，对于d ∈ {0, 1}，输入的所有点的第d维坐标不重复。所有操作涉及的集合非空。

输入格式

第一行一个整数N表示点数。 接下来N行，每行3个整数分别表示P_{i}的坐标与权值。 接下来一个整数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

题目来源

2014年国家集训队十五人互测 鸣谢Dragonite上传