前提
给若干个 \(n\) 维的点，对于每个点求出每一维均小于等于它的点的数量。
按字典序排序，然后预处理相同的点，这样后面的点不可能对前面的点产生贡献。
如果某个点后面有与其相同的点，那么当前点的贡献就会少算，所以我们需要提前在当前点的答案中加上后面与其相同的点的数量。
经过这样一通操作后，问题就变成了求前一个点前面的答案。
二维偏序
第一位单调不降，第二维用树状数组单点加一前缀求和维护。
考虑 CDQ 分治。
先将区间划分成两段，分别递归计算其内部的贡献，然后考虑前一段区间对后一段区间的贡献。
一开始整个区间第一维一定是单调不降的，第二维则是乱序的。在递归完成后，我们令两段区间第二维均是单调不降的，第一维则是乱序的。
因为递归前后并没有对区间进行任何修改，所以前一段区间第一维的最大值小于等于后一段区间第一维的最小值。而现在我们仅仅是考虑前一段区间对后一段区间的贡献，所以可以忽略第一维。
接着对两段区间分别维护一个指针，表示当前扫到哪里了。如果前一段区间指针指向的点的第二维小于等于后一段区间指针指向的点的第二维，说明前者可以对后者及其后面的所有点产生 \(1\) 的贡献，记录下来并将前一段区间的指针后移一位；否则说明后者已经不能被贡献到了，统计答案然后将后一段区间的指针后移一位。
返回时归并即可满足第二维要求。
三维偏序
依然上 CDQ 分治。做到第二维时，先不统计贡献，而是将点打上标记：前一段区间的点标记为 \(0\)，后一段区间的点标记为 \(1\)。在处理完后，我们再次 CDQ 分治。
第二维在 CDQ 分治时同样有只能从前一段区间贡献到后一段区间的要求，所以只有标记为 \(0\) 的点才能贡献到后面标记为 \(1\) 的点。多判断一下即可按照相同的方法统计答案。
多维偏序
来总结一下：
- 时刻保证只有前面的点对后面的点存在影响。
- 当前忽略的这一维在上一次 CDQ 分治中变得单调不降。
- 要统计的是前一段区间贡献到后一段区间，为当前 CDQ 分治打上属于哪个区间的标记。
- 最终统计答案时，标记均为 \(0\) 的点能贡献到标记均为 \(1\) 的点，其余均无效。
注意在归并的过程中，如果两区间当前元素相等，要优先放前一段的点，否则就会破坏最初排序后对于相同元素的特殊处理，也就是要保证稳定性。
标签：偏序,标记,笔记,贡献,学习,CDQ,一段,区间 From： https://www.cnblogs.com/landsol/p/17830622.html