由于太懒,我只学会了 cdq 分治解决逆序对问题.
例题 P3810
这样就得出了一个很重要的结论:在偏序问题中,只要有一位有序,那么就可以直接忽略这一维.这也为降维提供了可能性.
回到三维偏序问题,假设$a$有序,那么就可以直接忽略$a$的影响了;再考虑对$b$进行类似于归并排序的处理,同时使用 cdq 分治,对$c$构造一个权值树状数组,每次只需要统计$c_j\leq c_i$的个数即可.
另外,还有两个坑点:
树状数组在每次归并排序完成之后必须清空,否则会不停加下去;
$abc$全部相等的情况需要特判处理.
j--;