【模板】陌上花开——三位偏序

之前写过一篇cdq分治模拟树状数组
附上链接

然鹅属于二位偏序欸
三位偏序怎么做呢？
我们把第一位排好序忽略掉
剩下的在分治中用树状数组维护就好啦
大概思路如下：

1. 判边界，下放分治
2. 对当前范围按第二维，左边的第三维值插入树状数组，右边的查询
3. 像归并排序一样归位

代码如下

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int N = (int)2e6 + 5;

int n, m;

struct FW{
	int c[N];
	void ins(int x, int d){
		while(x <= m){
			c[x] += d;
			x += x & -x;
		}
	}
	int query(int x){
		int res = 0;
		while(x >= 1){
			res += c[x];
			x -= x & -x;
		}
		return res;
	}
	void print(){
		for(int i = 1; i <= m; ++i) printf("%d ", c[i]);
        printf("
");
	}
}fw;

struct A{
    int x, y, z, ans, size;	
}a[N], t[N];
int cnt[N], size[N];

bool rule_xyz(A x, A y){
	if(x.x != y.x) return x.x < y.x;
	if(x.y != y.y) return x.y < y.y;
	return x.z < y.z;
}//不要用<= 会爆炸！ 
bool rule_yzx(A x, A y){
	if(x.y != y.y) return x.y < y.y;
	if(x.z != y.z) return x.z < y.z;
	return x.x < y.x;
}

void cdq(int l, int r){
	if(r <= l) return ;
	//printf("%d %d
", l, r);
	int mid = l + ((r - l) >> 1);
	cdq(l, mid); cdq(mid + 1, r);
	//printf("l %d r %d
", l, r);
	
	sort(a + l, a + mid + 1, rule_yzx);
	sort(a + mid + 1, a + r + 1, rule_yzx);
	
	int i = l, j = mid + 1, tsize = 0;
	while(i <= mid && j <= r){
		if(a[i].y <= a[j].y){
			fw.ins(a[i].z, a[i].size);
			t[++tsize] = a[i++];
		}
		else {
			a[j].ans += fw.query(a[j].z);
			t[++tsize] = a[j++];
		}
	}
	while(i <= mid){ 
	    fw.ins(a[i].z, a[i].size);
		t[++tsize] = a[i++];
	}
	while(j <= r){
		a[j].ans += fw.query(a[j].z);
	//	printf("%d %d
", a[j].id, fw.query(a[j].z));
		t[++tsize] = a[j++];
	}
	for(i = l; i <= mid; ++i)
	    fw.ins(a[i].z, -a[i].size);
	for(i = 1; i <= tsize; ++i){
		a[l + i - 1] = t[i];
	}
    //fw.print();
}

int main() {
	freopen("flower.in", "r", stdin);
	scanf("%d%d", &n, &m); ++m;
	for(int i = 1; i <= n; ++i){
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z); ++a[i].z;
	}

	sort(a + 1, a + n + 1, rule_xyz);

    int tn = n; n = 0;
    for(int i = 1; i <= tn; ++i){
    	if(a[i].x == a[i - 1].x && a[i].y == a[i - 1].y && a[i].z == a[i - 1].z){
    		++a[n].size;
    	}
    	else {
    		a[++n] = a[i];
    		a[n].size = 1;
    	}
    }
	
	cdq(1, n);
    
	for(int i = 1; i <= n; ++i){
		a[i].ans += a[i].size - 1;//要记得考虑相等点的影响！
	    cnt[a[i].ans] += a[i].size;
	} 
	for(int i = 0; i < tn; ++i){
		printf("%d
", cnt[i]);
	}
	return 0;    
}