BZOJ 3262 陌上花开 三维偏序,CDQ分治

題意:长度为n的三元组序列(a,b,c), 对每个i询问有多少个j满足 ai>=aj && bi>=bj && ci>=cj.
n,a,b,c<=1e5.
第一维排序,然后对序列分治.

每次分治后对第二维进行归并,归并时考虑左区间对右区间的贡献,BIT维护第三维.O(n*logn*logn)

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node{
	int x,y,z,cnt,ans;
}a[N],b[N];
bool cmp(node a,node b){
	if(a.x==b.x){
		if(a.y==b.y)	return a.z<b.z;
		return a.y<b.y;
	}
	return a.x<b.x;
}
int n,m,k,c[N],res[N];
bool cmp1(node a,node b){
	if(a.y==b.y)	return a.z<b.z;
	return a.y<b.y;
}
int lowbit(int x){return x&-x;}
void update(int x,int val){
	for(int i=x;i<N;i+=lowbit(i))	c[i]+=val;
}
int query(int x){
	int res=0;
	for(int i=x;i>0;i-=lowbit(i))	res+=c[i];
	return res;
}
void cdq(int l,int r)
{
	if(l==r)	return;
	int mid=l+r>>1;
	cdq(l,mid),cdq(mid+1,r);
	sort(b+l,b+1+mid,cmp1),sort(b+mid+1,b+1+r,cmp1);
	int i=l,j=mid+1;
	while(j<=r)
	{
		while(i<=mid&&b[i].y<=b[j].y)	update(b[i].z,b[i].cnt),i++;
		b[j].ans+=query(b[j].z);
		j++;
	}
	for(int p=l;p<i;p++)	update(b[p].z,-b[p].cnt);
}
int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i].x>>a[i].y>>a[i].z;	
	sort(a+1,a+1+n,cmp);
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		cnt++;
		if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)	continue;
		else
		{
			b[++m]=a[i];
			b[m].cnt=cnt;
			cnt=0;
		}
	}
	cdq(1,m);
	for(int i=1;i<=m;i++)
		res[b[i].ans+b[i].cnt]+=b[i].cnt;	
	for(int i=1;i<=n;i++)
		cout<<res[i]<<'\n';
	return 0;
 }