裸题题面:给定n个点及其x、y坐标,统计每个点有多少点x、y坐标均小于该点
易想到树状数组统计逆序数对,故我们根据x坐标大小对点进行排序,以y坐标作为树状数组下标,一边读入一边统计(即二维偏序)
二维数点的应用:
https://www.luogu.com.cn/problem/P2163
大致题意:给定n颗树的x、y坐标,给定m个询问,询问给出一个矩形区域,求矩形内有多少树
根据容斥定理,我们可以预先处理出每个x、y坐标所对应的二维前缀和,可以达到O(1)查询
问题:坐标范围过大,若对每个坐标进行遍历是的复杂度,而就算对x、y坐标进行离散化仍无法通过
注意到我们不需要每个点的前缀和,故跟上题类似,我们对树的坐标、查询的坐标都根据x坐标进行排序(注意查询需要拆成4个点,且包含正负属性),我们对查询进行遍历,若当前统计的x坐标小于查询的x坐标,则继续统计直至当前统计的x坐标等于查询的x坐标,树状数组下标为y坐标,复杂度为O(nlogn),注意y坐标可能需要离散化
其实就是二维数点+容斥定理
延伸:CDQ分治—前置:归并排序,将事件(查询、修改)进行归并排序,在排序时统计前面事件的影响,用于数点问题,即将点按照x坐标排序,然后对y坐标进行归并排序