证明我还活着的博客。
前排提醒：这个东西不是我在搞，是我看到学弟们在搞。我只是看了看，然后就被震撼到了。唉，果然是后浪啊。
众所周知如果给定若干三维点 ((x_i,y_i,z_i))（为了方便，就假设所有 (x_i,y_i,z_i) 分别互不相同好了）可以 cdq 分治求出 (x_i < x_j,y_i<y_j,z_i<z_j) 的 ((i,j)) 对数。然后这样子是 (O(nlog^2 n)) 的。
然而可以考虑二项式反演。记 (f_k) 表示恰好有 (k) 维满足偏序，记 (g_k) 表示钦定 (k) 维满足偏序。那么有 (f_k=sum(-1)^{p-k}inom{p}{k}g_p)。
对于三维偏序有 (f_3=g_3,f_2=g_2-3g_3,f_1=g_1-2g_2+3g_3,f_0=g_0-g_1+g_2-g_3)。这其中 (g_0, g_1) 可以直接算，(g_2) 只需要做三次二维偏序，因此到这一步为止只需要 (O(nlog n)) 的时间。
然而未知元数量太多，考虑继续找等量关系，由对称性可得 (f_3=f_0,f_2=f_1)，于是就可以消出 (g_3)，然后就做完了。
至此，我们得到了三维偏序的 (O(nlog n)) 的做法。
然后是推广的问题，这个方法是否可以推广到 (k(k>3)) 维上呢？
学弟的博客好像说可以，但我没有看懂（QAQ），我自己算出的结果是：对于 (k) 为偶数的情况，该方法是不适用的，因为由对称性得到新等式中 (g_k) 的系数会被消成 0。
但是对于 (k) 为奇数的情况，可以变成求解若干次 (2sim k-1) 中所有偶数维偏序。
不过可以发现这个次数随 (k) 指数级增长，所以该优化方法可能在三维偏序中才能发挥它最大的效用。
“后生可畏，焉知来者之不如今也？”