#P3615. MSS

    ID: 2822 传统题 3000ms 512MiB 尝试: 128 已通过: 22 难度: 9 上传者: 标签>数据结构CF2800分块2014年国家集训队十五人互测鸣谢Dragonite上传

MSS

MSS

题目描述

小 C 要维护平面上的 NN 个点。第 ii 个点 PiP_i 有两个坐标和一个权值,初始时它单独属于编号为 ii 的集合 SiS_i。

需要按顺序处理四种操作。

  • Merge x y 把集合 SyS_y 中的点移到集合 SxS_x。
  • Split i d v 创建两个新的集合 Sc+1,Sc+2S_{c+1},S_{c+2}。这里 cc 是此前分配过的集合编号总数,包括已经变为空集的集合。把 SiS_i 中第 dd 维坐标不超过 vv 的点移入 Sc+1S_{c+1},其余点移入 Sc+2S_{c+2}。d=0d=0 表示横坐标,d=1d=1 表示纵坐标。
  • Query i 询问集合 SiS_i 内点权的最大值、最小值和总和。
  • Add i d 将集合 SiS_i 内所有点的权值增加 dd。

合并、分割和增加权值均不改变点的坐标。全部点的横坐标两两不同,纵坐标也两两不同。作为操作对象的集合保证非空。

输入格式

第一行一个整数 NN。接下来 NN 行,每行三个整数,依次为该点的横坐标、纵坐标和初始权值。

接下来一行一个整数 QQ,表示操作数。随后 QQ 行各给出一个操作,格式见题目描述。

输出格式

每遇到一次 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

数据范围

N≤50000N\le50000,Q≤100000Q\le100000。