科技——O(n log n) 三维偏序

问题背景

有 \(n\) 个三元组 \((a_i,b_i,c_i)\)，要求满足 \(a_i\le a_j,b_i\le b_j,c_i\le c_j\) 的有序对 \((i,j)\) 数量。
保证不存在两个三元组相同。（存在相同的情况下面会说）。
介绍

因为不会出现重复的数，所以不需要考虑 \((i,j)\) 互相偏序的情况。
设 \(f_i\) 表示恰好 \(i\) 维偏序的对数，\(g_i\) 表示钦定 \(i\) 维偏序的对数。
那么 \(g_i=\sum_{j=i}^3 C_j^i \times f_j\)，二项式反演得 \(f_i=\sum_{j\ge i} (-1)^{j-i} \times C_j^i \times g_j\)。
所以：\(f_0=g_0-g_1+g_2-g_3\)。
即 \(g_3=g_0-f_0-g_1+g_2\)。
而 \(g_3=f_3\)，所以 \(f_3=g_0-f_0-g_1+g_2\)。
\(g_0\) 和 \(g_1\) 直接 \(O(1)\) 和 \(O(n)\) 求，\(g_2\) 做三次二维偏序就可以了。
主要是 \(f_0\) 怎么算。
注意到现在偏序条件是 \(\le\) 所以 \(f_0\) 不一定 \(=f_3\)。
比如 \((4,4,4)\) 确实三维偏序 \((2,4,4)\) 但是 \((2,4,4)\) 有两维是偏序 \((4,4,4)\) 的。
所以如果我们能让每一维都变成互不相同的就可以保证 \(f_0=f_3\) 了。
也就是说 \(f_3=\frac{g_0-g_1+g_2}{2}\)。
那怎么办呢？
其实只需要分别按某一维为第一关键字排序，其他两维为二，三关键字排序。
将这种条件下的每个三元组的排名作为这一维新的值就可以了。
举个例子： 我们有三个三元组 \((4,4,2),(2,4,4),(4,4,4)\)。

• 先按照第一维为第一关键字，二，三维为第二，三关键字排序：\((2,4,4),(4,4,2),(4,4,4)\)。
  然后用现在的排名替换第一维：\((1,4,4),(2,4,2),(3,4,4)\)。
  
• 再按照第二维为第一关键字，一，三维为第二，三关键字排序：\((1,4,4),(2,4,2),(3,4,4)\)。
  然后用现在的排名替换第二维：\((1,1,4),(2,2,2),(3,3,4)\)。
  
• 最后按照第三维为第一关键字，一，二维为第二，三关键字排序：\((2,2,2),(1,1,4),(3,3,4)\)。
  然后用现在的排名替换第三维：\((2,2,1),(1,1,2),(3,3,3)\)。
  

容易证明这样每一维都是排列，并且不会影响 \(f_3\) 最终的值。(但显然会影响 \(f_0,f_1,f_2\)，反正你也不去管这三个值)。
具体看最后给出的代码。
而且在这种情况下，\(g_0,g_1\) 都是可以 \(O(1)\) 算的。
代码可能比 CDQ 分治还好写。
补充说明

• 如果会出现相同的三元组怎么办？
  相同的三元组答案肯定一样，可以把他们缩到一起（类似于洛谷模板题的处理思路），然后在最后算答案的时候再加上互相偏序的三元组的贡献。
  
• 如果某一维要求 \(\ge\) 怎么办？
  把那一维全部取反即可。
  

局限性

• 不能像 CDQ 分治那样算出每个三元组具体偏序了多少其他三元组。
  
• 偏序条线必须包含 =，即不能处理 > 类型的偏序。
  这一点也很好证明，因为不管你的要求是什么，按照那种方法变换之后的序列都是一样的，无法区分 \(>\) 和 \(\ge\)。
  而如果你不变换的话，\((2,4,4)\) 没有一维是偏序 \((4,4,4)\) 的，但是 \((4,4,4)\) 并不是三维偏序 \((2,4,4)\) 的。
  所以 \(f_0\ne f_3\)。
  

下面通过一道典题来给出代码。
例题

题面

给你 \(n\) 个三元组，问有几个有序对 \((i,j)\) 满足第 \(i\) 个三元组可以经过若干次操作变成第 \(j\) 个三元组。
一次操作定义为：选一个数 \(-1\) 再把令两个数 \(+1\)。
\(n\le 2e6\)。
题解

解个方程就知道 \((d,e,f)\) 可以变成 \((a,b,c)\) 的条件是下面三个数都是非负偶数：

• \(a+b-d-e\)
  
• \(a+c-d-f\)
  
• \(b+c-e-f\)。
  

然后用 \((a+b,a+c,b+c)\) 代替 \((a,b,c)\) 根据奇偶性分成 \(8\) 组，每组里面跑三维偏序就可以了。
因为 \(n\le 2e6\) 所以你只能写 \(O(n\log n)\)。
code

[code]#include#define LL long long using namespace std;                                 const int N=2e6+5;inline int read(){        int w=1,s=0;        char c=getchar();        for(;c'9';w*=(c=='-')?-1:1,c=getchar());        for(;c>='0'&&c