洛谷 - P3810 【模板】三维偏序（陌上花开）(CDQ分治套树状数组)

题目链接：点击查看

题目大意：给出 n 个点，每个点有三个属性 a , b , c ，对于每个点 i 来说，求出有多少个 j 满足 a[ j ] <= a[ i ] && b[ j ] <= b[ i ] && c[ j ] <= c[ i ]

题目分析：三维偏序的模板问题，咕咕咕了有一年的CDQ分治，今天终于补出来了，简单总结一下，一维偏序排个序就出来了，二维偏序是对一维排序，另一维用线段树或树状数组维护，三维的话，第一维排序，第二维用归并排序维护，第三维用线段树维护，在归并排序的过程中计算贡献就好了

代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;
 
typedef long long LL;
 
typedef unsigned long long ull;
 
const int inf=0x3f3f3f3f;
 
const int N=2e5+100;

struct Node
{
	int a,b,c,f,w;
	bool operator==(const Node& t)const
	{
		return a==t.a&&b==t.b&&c==t.c;
	}
	bool operator<(const Node& t)const
	{
		if(a!=t.a)
			return a<t.a;
		if(b!=t.b)
			return b<t.b;
		return c<t.c;
	}
}a[N],t[N];

int c[N],ans[N],n,k;

int lowbit(int x)
{
	return x&(-x);
}

void add(int pos,int val)
{
	while(pos<=k)
	{
		c[pos]+=val;
		pos+=lowbit(pos);
	}
}

int ask(int pos)
{
	int ans=0;
	while(pos)
	{
		ans+=c[pos];
		pos-=lowbit(pos);
	}
	return ans;
}

void CDQ(int l,int r)
{
	if(l==r)
		return;
	int mid=l+r>>1;
	CDQ(l,mid);
	CDQ(mid+1,r);
	int p=l,q=mid+1,tot=l;
	while(p<=mid&&q<=r)
	{
		if(a[p].b<=a[q].b)
		{
			add(a[p].c,a[p].w);
			t[tot++]=a[p++];
		}
		else
		{
			a[q].f+=ask(a[q].c);
			t[tot++]=a[q++];
		}
	}
	while(p<=mid)
	{
		add(a[p].c,a[p].w);
		t[tot++]=a[p++];
	}
	while(q<=r)
	{
		a[q].f+=ask(a[q].c);
		t[tot++]=a[q++];
	}
	for(int i=l;i<=mid;i++)
		add(a[i].c,-a[i].w);
	for(int i=l;i<=r;i++)
		a[i]=t[i];
}

int unique()
{
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]==a[i-1])
			a[cnt].w++;
		else
			a[++cnt]=a[i];
	}
	return cnt;
}

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	scanf("%d%d",&n,&k);
	int nn=n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
		a[i].w=1;
	}
	sort(a+1,a+1+n);
	n=unique();
	CDQ(1,n);
	for(int i=1;i<=n;i++)
		ans[a[i].f+a[i].w-1]+=a[i].w;
	for(int i=0;i<nn;i++)
		printf("%d\n",ans[i]);











   return 0;
}