[bzoj1935][Shoi2007]Tree 园丁的烦恼 _树状数组
2021-07-11 12:04
标签:algorithm $1 lin void def 二维树状数组 turn 表示 puts
Tree 园丁的烦恼 bzoj-1935 Shoi-2007
题目大意:给定平面上的$n$个点,$m$次查询矩形点个数。
注释:$1\le n,m\le 5\cdot 10^5$。
想法:静态二维数点。
$Orz Winniechen$,真tm敢写$KD-Tree$,虽然$T$了..
正常这种静态的二维数点我们都要请到树状数组。最简单的就是二维树状数组。
但是发现开不下,这样的话我们依据它可以离线这一点,我们将每个询问$(x1,y1)$到$(x2,y2)$变成$4$次查询:
$(x1-1,y1-1),(x1-1,y2),(x2,y1-1),(x2,y2)$把它们哥四个都当成点放入点集。每次都相当于查询$(1,1)$到$balabala$
每个点集中的点有$4$个参数:横纵坐标,种类和系数。
种类就是这个点到底是给定的点还是查询的点。
系数的话就是容斥前面的系数:$(x1-1,y1-1)$和$(x2,y2)$前面是$1$,$(x1-1,y2)$和$(x2,y1-1)$前面是$-1$。
然后我们将点集排序,横坐标递增为第一关键字,纵坐标递增为第二关键字。
紧接着我们顺次枚举每个点,如果这个点的种类是给定点,我们将它压到树状数组里。
是一个树状数组里,我们只开一个树状数组,记录的是小于每个横坐标的点的个数。
这样的话根据我们的关键字可知,每一个有可能更新查询的点都会被提前枚举过。
如果这个点是查询,就直接查询然后累加到对应查询的编号答案上,即可。
最后,附上丑陋的代码... ...
#include#include #include #include #define N 1000010 using namespace std; struct Node { int x,y,f,id;//这里跟上述的有些不一样。 //我们用f直接可以同时记录种类和系数。如果f==0,那么就表示这个点是给定的点,反之f=1或-1代表系数,直接累计即可。 }q[N=1;i-=lowbit(i)) { ans+=tree[i]; } return ans; } int main() { int n,m; cin >> n >> m ; for(int i=1;i
小结:这个想法极其常用,很多静态可离线二维数点问题都可以用这个来解决。那些动态的就让KD-Tree上吧,反正出了那种题被卡常的不可能只有你一个人/手动滑稽
[bzoj1935][Shoi2007]Tree 园丁的烦恼 _树状数组
标签:algorithm $1 lin void def 二维树状数组 turn 表示 puts
原文地址:https://www.cnblogs.com/ShuraK/p/9551444.html
文章标题:[bzoj1935][Shoi2007]Tree 园丁的烦恼 _树状数组
文章链接:http://soscw.com/essay/103686.html