F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 3615. -- MSS

3615: MSS

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 126  Solved: 33
[Submit][Status][Discuss]

Description

 小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维坐标不重复。所有操作涉及的集合非空。

Input

  第一行一个整数N表示点数。
  接下来N行,每行3个整数分别表示Pi的坐标与权值。
  接下来一个整数Q表示操作数。
  接下来Q行,每行描述一个操作,格式如上所述。

Output

  对于每个Q操作,输出三个整数,依次表示询问集合权值的最大值,最小值与和。

Sample Input

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

Sample Output

10 5 15
1 1 1
3 3 3
3 3 3

HINT

N<=50000


Q<=100000

Source

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

[Submit][Status][Discuss]

HOME Back