#P3592. Architext
Architext
Architext
题目描述
建筑师 Silly Hook 设计别墅时,决定利用土地上已有的洞作为地基的基点。他还请来 Shabby Hook 帮忙填洞;与此同时,捣乱的人也可能继续挖洞。土地上最初有 个洞,编号为 至 。事件按输入顺序发生。
H x d:将第 号洞的深度加上 。 表示填浅, 表示加深。A m x_1 ... x_m:询问依次以洞 为顶点的区域。多边形的顶点按顺时针顺序给出;当 时,区域为两端点之间的线段。计算该区域内所有洞的深度之和,以及最大的深度。边界上的洞也计入。
多边形不会自交。所有询问的边合在一起构成一个以洞为顶点的连通平面图。不同询问可以共用洞或整条边;不同的边只在共同端点处相接。
输入格式
第一行一个整数 ,表示数据点编号。第二行一个整数 ,表示洞数。接下来 行,每行三个整数 ,表示一个洞的坐标和初始深度。
接下来一行一个整数 ,表示事件数。其后 行,按题述格式给出事件。
输出格式
对于每个 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
数据范围
,。各次非线段的多边形询问所给出的顶点数之和不超过 。