一般的静态二维数点问题:
给出平面上的\(n\)个点的坐标\(P_i(x_i,y_i)\),\(Q\)次查询,每次查询\(a,b,c,d\)表示求在矩形\((a,b),(c,d)\)中的点数。
假设\(a,b,c,d<=10^5\)
那么此时数据范围都是\(10^5\)级别的,显然是不能再用前缀和来解决问题了,但是我们还是可以用二维前缀和的思想:
假设\(S(x,y)\)表示\(0,0),(x,y)\)这个矩阵中的点数,那么每次查询\(a,b,c,d\)的答案即为\(S(x,y)-S(a-1,d)-S(c,b-1)+S(c-1,d-1)\)
//解释见右图
如此我们便可以将原先的问题拆成这四部分的解来分别解决,这就是分治的基本思想:将一个问题分成几个可以相加的小问题来解决。
之后的做法,就是用扫描线(这个可以看我以前的文章 https://www.luogu.org/blog/tongli/solution-uva1398,原题的传送门
https://www.luogu.org/problem/UVA1398这道题比较水,是一道扫描线的模板题,大家可以去看一下!)
先将所有的点和拆分后的每一个询问全部按照其\(x\)进行排序,之后每次扫描线扫到一个询问\(x\),就把当前还剩下的小于\(x\)的点全部加上这个点再\(y\)轴的贡献(感性理解一下就是我们把树状数组的下标看作权值,当前影响的是\(1-y\)这个范围的点,所以该区间的贡献在树状数组上\(+1\)。当然上面是离线的情况下,如果是在线的,使用主席树维护即可。
//在此我挖个坑:我一定要把线段树的博客补了!请务必监督我!
做一道例题:https://www.luogu.org/problemnew/show/P2163
标准的板题!
2020/04/09:这篇文章本来的重点是动态二维数点,但是着实是咕的太久了,以至于我一直没有写它,现在我退役了,也不会了,也懒得写了,把静态的先发出来吧。