[BZOJ4066/Luogu4148]简单题(KDT)

发布于 2018-05-14  166 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4066/Luogu4148]简单题(KDT)

Description

你有一个 N×NN \times NN×N 的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:
1 x y A 1≤x,y≤N1\le x,y\le N1≤x,y≤N$$ ,A是正整数。将格子x,y里的数字加上 AAA
2 x1 y1 x2 y2 1≤x1≤x2≤N1 \le x_1 \le x_2 \le N1≤x1​≤x2​≤N , 1≤y1≤y2≤N1 \le y_1\le y_2 \le N1≤y1​≤y2​≤N 。输出 x1,y1,x2,y2x_1, y_1, x_2, y_2x1​,y1​,x2​,y2​ 这个矩形内的数字和
3 无 终止程序

Tag

KDT

解决思路

用KDT维护暴力查找点是否在矩形内部。具体来说,若当前KDT结点维护的矩形与查询矩形没有交,则直接退出。若当前矩形整个完全包含于查询矩形中,则直接返回整个矩形的和。
至于插入操作,按照KDT的排序方式插入,每10000重构一次。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4066/Luogu4148]简单题(KDT)


HNCJ OIer