問題背景

有 \(n\) 個三元組 \((a_i,b_i,c_i)\)，要求滿足 \(a_i\le a_j,b_i\le b_j,c_i\le c_j\) 的有序?qū)?\((i,j)\) 數(shù)量。
保證不存在兩個三元組相同。（存在相同的情況下面會說）。

介紹

因為不會出現(xiàn)重復(fù)的數(shù)，所以不需要考慮 \((i,j)\) 互相偏序的情況。

設(shè) \(f_i\) 表示恰好 \(i\) 維偏序的對數(shù)，\(g_i\) 表示欽定 \(i\) 維偏序的對數(shù)。
那么 \(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\) 怎么算。
注意到現(xiàn)在偏序條件是 \(\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}\)。

那怎么辦呢？
其實只需要分別按某一維為第一關(guān)鍵字排序，其他兩維為二，三關(guān)鍵字排序。
將這種條件下的每個三元組的排名作為這一維新的值就可以了。
舉個例子： 我們有三個三元組 \((4,4,2),(2,4,4),(4,4,4)\)。

1. 先按照第一維為第一關(guān)鍵字，二，三維為第二，三關(guān)鍵字排序：\((2,4,4),(4,4,2),(4,4,4)\)。
   然后用現(xiàn)在的排名替換第一維：\((1,4,4),(2,4,2),(3,4,4)\)。
2. 再按照第二維為第一關(guān)鍵字，一，三維為第二，三關(guān)鍵字排序：\((1,4,4),(2,4,2),(3,4,4)\)。
   然后用現(xiàn)在的排名替換第二維：\((1,1,4),(2,2,2),(3,3,4)\)。
3. 最后按照第三維為第一關(guān)鍵字，一，二維為第二，三關(guān)鍵字排序：\((2,2,2),(1,1,4),(3,3,4)\)。
   然后用現(xiàn)在的排名替換第三維：\((2,2,1),(1,1,2),(3,3,3)\)。

容易證明這樣每一維都是排列，并且不會影響 \(f_3\) 最終的值。(但顯然會影響 \(f_0,f_1,f_2\)，反正你也不去管這三個值)。
具體看最后給出的代碼。

而且在這種情況下，\(g_0,g_1\) 都是可以 \(O(1)\) 算的。

代碼可能比 CDQ 分治還好寫。

補充說明

1. 如果會出現(xiàn)相同的三元組怎么辦？
   相同的三元組答案肯定一樣，可以把他們縮到一起（類似于洛谷模板題的處理思路），然后在最后算答案的時候再加上互相偏序的三元組的貢獻。

2. 如果某一維要求 \(\ge\) 怎么辦？
   把那一維全部取反即可。

局限性

1. 不能像 CDQ 分治那樣算出每個三元組具體偏序了多少其他三元組。

2. 偏序條線必須包含 =，即不能處理 > 類型的偏序。
   這一點也很好證明，因為不管你的要求是什么，按照那種方法變換之后的序列都是一樣的，無法區(qū)分 \(>\) 和 \(\ge\)。
   而如果你不變換的話，\((2,4,4)\) 沒有一維是偏序 \((4,4,4)\) 的，但是 \((4,4,4)\) 并不是三維偏序 \((2,4,4)\) 的。
   所以 \(f_0\ne f_3\)。

下面通過一道典題來給出代碼。

例題

題面

給你 \(n\) 個三元組，問有幾個有序?qū)?\((i,j)\) 滿足第 \(i\) 個三元組可以經(jīng)過若干次操作變成第 \(j\) 個三元組。
一次操作定義為：選一個數(shù) \(-1\) 再把令兩個數(shù) \(+1\)。
\(n\le 2e6\)。

題解

解個方程就知道 \((d,e,f)\) 可以變成 \((a,b,c)\) 的條件是下面三個數(shù)都是非負偶數(shù)：

1. \(a+b-d-e\)
2. \(a+c-d-f\)
3. \(b+c-e-f\)。

然后用 \((a+b,a+c,b+c)\) 代替 \((a,b,c)\) 根據(jù)奇偶性分成 \(8\) 組，每組里面跑三維偏序就可以了。
因為 \(n\le 2e6\) 所以你只能寫 \(O(n\log n)\)。

code

#include<bits/stdc++.h>
#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<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
	for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
	return w*s;
}
int n;
struct P{
	int a,b,c;
}p[N];
struct Work{  //三維偏序
	int n=0;
	struct BIT{
		int c[N];
		void init(){memset(c,0,sizeof c);}
		void add(int i,int x,int n){for(;i<=n;i+=(i&(-i))) c[i]+=x;}
		int ask(int i){
			int sum=0;
			for(;i;i-=(i&(-i))) sum+=c[i];
			return sum;
		}
	}Bit;
	struct P{
		int val[3];
	}a[N];
	void insert(int x,int y,int z){a[++n].val[0]=x,a[n].val[1]=y,a[n].val[2]=z;}
	
	LL calc1(int id){ return 1ll*n*(n-1)/2ll; }   //注意到每一維都是排列的情況下，欽定一維偏序的數(shù)目可以 O(1) 求
	LL solve1(){return calc1(0)+calc1(1)+calc1(2);}
	LL calc2(int o1,int o2){
		sort(a+1,a+n+1,[&](P u,P v){return u.val[o1]<v.val[o1];});  
		LL res=0;
		Bit.init();
		for(int i=1;i<=n;i++){
			res+=Bit.ask(a[i].val[o2]);
			Bit.add(a[i].val[o2],1,n);
		}
		return res;
	}
	LL solve2(){return calc2(0,1)+calc2(1,2)+calc2(0,2);}
	void Sort(int o1,int o2,int o3){
		sort(a+1,a+n+1,[&](P u,P v){
			if(u.val[o1]!=v.val[o1]) return u.val[o1]<v.val[o1];
			if(u.val[o2]!=v.val[o2]) return u.val[o2]<v.val[o2];
			return u.val[o3]<v.val[o3];
		});
		for(int i=1;i<=n;i++) a[i].val[o1]=i;  //將排名賦值給這一維
	}
	LL work(){ 
		Sort(0,1,2),Sort(1,0,2),Sort(2,0,1);  //重新賦值使得每一維是排列。
		return (1ll*n*(n-1)-solve1()+solve2())/2ll; 
	}
}t[8];
void work(){
	for(int i=1;i<=n;i++){
		int x=p[i].b+p[i].c;	
		int y=p[i].a+p[i].c;	
		int z=p[i].b+p[i].a;	
		t[((x&1)<<2)+((y&1)<<1)+(z&1)].insert(x,y,z);
	}
	LL ans=0;
	for(int i=0;i<8;i++) ans+=t[i].work();
	printf("%lld\n",ans);
}
signed main(){
	freopen("eden.in","r",stdin);
	freopen("eden.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		p[i]={read(),read(),read()};
	}
	work();
	return 0;
}

CDQ 分治并不會被替代，這是好的。