【模板】三维偏序（陌上花开）

题目

求满足 (a_i leq a_j，b_i leq b_j，c_i leq c_j) 的三元组的个数
输出个数范围为 ([0..n-1]) 的每种个数出现的次数

解析

(cdq) 分治版题，三维数点
先让第一维排序，然后归并思想排序第二维
考虑分治的左区间对右区间的贡献
每次用左区间的点更新右区间点的答案
特别注意如果一个点与另一个点三个属性都相同
由于我们是算他左边点对他的贡献
所以我们最后记录最终的答案时取三个属性都相同排在最后的

(Code)

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 2e5 + 5;
int n , k , ans[N] , c[N];

struct node{
	int a , b , c , f;	
}fl[N] , nfl[N];

inline bool cmp(node x , node y)
{
	if (x.a == y.a)
	{
		if (x.b == y.b) return x.c < y.c;
		return x.b < y.b;
	}
	return x.a < y.a;
}

inline int lowbit(int x){return x & (-x);}
inline void add(int x , int v){for(; x <= k; x += lowbit(x)) c[x] += v;}

inline int query(int x)
{
	int res = 0;
	for(; x; x -= lowbit(x)) res += c[x];
	return res;
}

inline void solve(int l , int r)
{
	if (l == r) return;
	int mid = (l + r) >> 1;
	solve(l , mid) , solve(mid + 1 , r);
	int i = l , j = mid + 1 , k = l;
	while (i <= mid && j <= r)
	{
		if (fl[i].b <= fl[j].b) add(fl[i].c , 1) , nfl[k++] = fl[i] , i++;
		else fl[j].f += query(fl[j].c) , nfl[k++] = fl[j] , j++;
	}
	while (i <= mid) add(fl[i].c , 1) , nfl[k++] = fl[i] , i++;
	while (j <= r) fl[j].f += query(fl[j].c) , nfl[k++] = fl[j] , j++;
	for(register int p = l; p <= mid; p++) add(fl[p].c , -1);
	for(register int p = l; p <= r; p++) fl[p] = nfl[p];
}

int main()
{
	scanf("%d%d" , &n , &k);
	for(register int i = 1; i <= n; i++) scanf("%d%d%d" , &fl[i].a , &fl[i].b , &fl[i].c);
	sort(fl + 1 , fl + n + 1 , cmp);
	solve(1 , n);
	for(register int i = 1; i <= n; i++)
	{
		int j = i;
		while (fl[i].a == fl[i + 1].a && fl[i].b == fl[i + 1].b && fl[i].c == fl[i + 1].c && i < n) i++;
		ans[fl[i].f] += i - j + 1;
	}
	for(register int i = 0; i < n; i++) printf("%d
" , ans[i]);
}