高维偏序学习笔记

Lucky_Xiang · 2024-01-21 21:24:40 · 算法·理论

二维数点

二维平面内有许多点，询问一个矩形内有多少个点。

按照 y 坐标从小到大将点加入所有点，用线段树或树状数组维护 x 坐标上有多少个点，将询问拆成若干个矩形的容斥即可。

三维偏序

CDQ 分治

不妨假设所有点互不相同。

先将所有点按照 (x,y,z) 排序，这样可以减少一维。

再采用分治（将 y 归并排序），合并区间时相当于是按照 y 从小到大加入点，可以解决 y 这一维度。

最后一维 z 可以使用树状数组维护。

总复杂度 O(n\log^2 n)。

树套树

不妨假设所有点互不相同。

先将所有点按照 (x,y,z) 排序，这样可以减少一维。

按照这个顺序加点。采用线段树或树状数组套线段树的方式，外层树的一个节点表示满足 y\in[L,R] 条件的 z 信息被存储在它的内层树中；内层树采用动态开点线段树，维护 z 信息。这样可以做到单点加入，矩阵查询，时间复杂度 O(n\log^2n)。

容斥

不妨假设所有点互不相同。

因为所有点互不相同，所以可以先将点按照 (x,y,z) 进行排序。将排名加权到 x,y,z 之中，这样 x,y,z 也会变得互不相同。

我们要求出 \sum_{i\ne j}[x_i\le x_j][y_i \le y_j][z_i\le z_j] 的值。不妨设这三个条件中恰好满足 P 条件的有 F_P 组，而不满足 P 条件的有 G_P 组。

那么：

因为 x,y,z 已经互不相同，所以 F_{x,y,z}=G_{x,y,z}。

我们知道 U=n(n-1)，G_x=G_y=G_z={1\over2}n(n-1)。而 G_{x,y},G_{y,z},G_{z,x} 就是个二维偏序。所以可以用 O(n\log n) 的复杂度完成。