#P3592. Architext

    ID: 2794 传统题 3000ms 256MiB 尝试: 175 已通过: 11 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS图论平面图对偶排序与序列处理自定义排序规则计算几何叉积离线与分治线段树分治活跃时间区间挂树数据结构可撤销并查集按大小合并CF30002014年国家集训队十五人互测By

Architext

Architext

题目描述

建筑师 Silly Hook 设计别墅时,决定利用土地上已有的洞作为地基的基点。他还请来 Shabby Hook 帮忙填洞;与此同时,捣乱的人也可能继续挖洞。土地上最初有 nn 个洞,编号为 11 至 nn。事件按输入顺序发生。

  • H x d:将第 xx 号洞的深度加上 dd。d<0d<0 表示填浅,d>0d>0 表示加深。
  • A m x_1 ... x_m:询问依次以洞 x1,…,xmx_1,\ldots,x_m 为顶点的区域。多边形的顶点按顺时针顺序给出;当 m=2m=2 时,区域为两端点之间的线段。计算该区域内所有洞的深度之和,以及最大的深度。边界上的洞也计入。

多边形不会自交。所有询问的边合在一起构成一个以洞为顶点的连通平面图。不同询问可以共用洞或整条边;不同的边只在共同端点处相接。

输入格式

第一行一个整数 Case\mathrm{Case},表示数据点编号。第二行一个整数 nn,表示洞数。接下来 nn 行,每行三个整数 x,y,dx,y,d,表示一个洞的坐标和初始深度。

接下来一行一个整数 qq,表示事件数。其后 qq 行,按题述格式给出事件。

输出格式

对于每个 A 事件,输出一行两个整数,依次为所询问区域内洞的深度总和和最大深度。

样例

0
6
1 1 1
2 2 1
2 3 1
2 4 1
2 5 1
4 1 1
6
A 3 1 2 6
A 3 1 3 6
A 3 1 4 6
A 3 1 5 6
A 3 1 3 2
A 3 2 3 6
3 1
4 1
5 1
6 1
3 1
3 1

数据范围

n,q≤5×104n,q\le5\times10^4,∣x∣,∣y∣≤107|x|,|y|\le10^7。各次非线段的多边形询问所给出的顶点数之和不超过 160000160000。