一种离线处理多维偏序问题的算法。

洛谷p3810

三维空间中给定 $n$ 个点，编号为 $1 \sim n$。定义 $f[i]$ 表示恰好有 $i$ 个元素满足 $x_i\le x_j,y_i\le y_j,z_i\le z_j$ 且 $i\ne j$ 的 $j$ 的个数。

要求输出 $f[0 \sim n-1]$。

先考虑所有元素互异的情况。

先将第一维作为第一关键字，第二维作为第二关键字，第三维作为第三关键字对序列进行第一轮排序。

排序后将第二维作为第一关键字，第三维作为第二关键字对序列进行归并排序，利用分治过程计算答案贡献。

分治过程中受第一轮排序结果影响，只有左区间元素能为右区间元素做贡献，而右区间不能为左区间做贡献。