首页 > 试题广场 >

枇杷

[编程题]枇杷
庭有枇杷树,吾妻死之年所手植也,今已亭亭如盖矣。
矩梯形是尝最好之形。
孩提时,尝共之植枇杷树。
今人亡琴在,其只记在何处栽之,而不知某梯形内凡几树。
其得君,其小仆,请告之所欲知梯形内凡几树。
换言之,你需要在一个平面直角坐标系中支持以下两个操作:
1. 将点 (x,y) 的权值加 1
2. 询问一个直角梯形内所有点的权值和,即以 (x1,y1) 为左下角,(x1,y1+d) 为左上角, (x2,y1+d) 为右上角,(x2+d,y1) 为右下角形成的直角梯形。直角梯形的边界也计入答案。
你可以认为所有活动都在坐标系的第一象限且不与坐标轴相交。

输入描述:
第一行一个整数 n,表示接下来有 n 个操作。
接下来 n 行,每行的格式为 1 x y 或 2 x1 y1 x2 d。
如果第一个数为 1,表示将 (x,y) 的权值加 1。
否则为询问。


输出描述:
对于每个询问,输出对应的直角梯形内部的点权和。
示例1

输入

6
1 1 2
1 1 3
1 3 2
2 1 2 2 1
1 3 4
2 1 2 3 2

输出

3
4

备注:
n<=100000,1<=x1,x2,y1,d<=109
数据保证 x1<x2
注意,x2+d,y1+d有可能大于109
保证数据全部随机生成
头像 耕云种月
发表于 2022-01-30 19:24:54
原题解链接: 题面有个隐含条件是直角梯形的三角形部分是等腰直角三角形,问题转化为求矩形+等腰直角三角形点权和。 对于所有在等腰直角三角形斜边上的点(x,y)(x,y)(x,y),满足x+yx + yx+y是一个定值kkk。 考虑CDQCDQCDQ分治求矩形内部点权和的过程,如果以横坐标为排序的第一关 展开全文