偏序问题

一维偏序

归并排序即可。

二维偏序*

又称“二维数点”，只需按照 x 坐标排序后按照一维偏序的方法即可。

三维偏序

考虑按照 \(x\) 排序，设左右两边分别为 \(L\) 和 \(R\) ，此时对于 \(i\in L,j\in R\)，存在 \(x_i<x_j\)，我们已经圧掉了一维。考虑如何圧掉第二维。明显，\(L\) 中的点都有可能对 \(j\) 产生贡献。我们分别在 \(L\) 和 \(R\) 按照 \(y\) 排序。注意，我们目前只考虑 \(L\) 对 \(j\) 的贡献，\(R\) 中的点对 \(j\) 的贡献会在分治中得到体现。设排序后 \(L\) 部分为 \(l_1,l_2,l_3,\ldots ,l_{mid}\) ，\(R\) 部分同理。先只考虑 \(r_1\)。把 \(i\) 作为 \(L\) 部分的指针，直到枚举到第一个 \(l_i.y>r_1.y\)，枚举过程中把 \(l_i.z\) 放入树状数组，统计答案。对于 \(r_2\) ，显然可以延续 \(r_1\) 查询过程中在树状数组上的成果，然后按照刚才的逻辑移动指针即可。

注意，当一次处理完成后要合并区间时，要注意清空树状数组，小常数写法（from syz）：

struct fenwick{
	int c[N],vis[N],ti;
	fenwick(){
		memset(c,0,sizeof(c));
		memset(vis,0,sizeof(vis));
	}
	inline void add(int x,int w){
		while(x<=k){
			if(vis[x]!=ti) vis[x]=ti,c[x]=0;
			c[x]+=w;
			x+=lowbit(x);
		}
	}
	inline int sum(int x){
		int res=0;
		while(x){
			res+=c[x]*(vis[x]==ti);
			x-=lowbit(x);
		}
		return res;
	}
	inline void clear(){
		ti++;
	}
}BIT;

运用了可持久化的思想。
然后一个 c[x]，我们记录一下其最后一次被修改的时间 ti
如果 ti[x]!=nowti，那么说明这个位置无效