欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P3810-[模板]三维偏序(陌上花开)【CDQ分治,树状数组】

程序员文章站 2022-05-14 18:42:09
...

正题

题目链接:https://www.luogu.com.cn/problem/P3810


题目大意

nn个三元组(a,b,c)(a,b,c)f(i)=i=1n,ji[ajai&bjbi&bjbi]f(i)=\sum_{i=1}^{n,j\neq i}[a_j\leq a_i\&b_j\leq b_i\&b_j\leq b_i]

对于每个dd,求有多少个f(i)=df(i)=d


解题思路

先按照aa排序,然后对于bb这一维进行CDQCDQ分治,之后用树状数组计算cc这一维的结果即可。

要注意的是统计f(i)f(i)的时候要在结构体里,不然它不会随着排序而交换。

时间复杂度O(nlog2n)O(n\log^2n)


codecode

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
struct node{
	int a,b,c,w,ans;
}a[N],b[N];
int n,m,k,ask[N];
struct Tree_Array{
	#define lowbit(x) (x&-x)
	int t[N];
	void Change(int x,int z){
		while(x<=k){
			t[x]+=z;
			x+=lowbit(x);
		}
	}
	int Ask(int x){
		int ans=0;
		while(x){
			ans+=t[x];
			x-=lowbit(x);
		}
		return ans;
	}
	#undef lowbit(x)
}Ta;
bool Cmp(node x,node y){
	if(x.a!=y.a) return x.a<y.a;
	return (x.b==y.b)?(x.c<y.c):(x.b<y.b);
}
bool cMp(node x,node y)
{return (x.b==y.b)?(x.c<y.c):(x.b<y.b);}
void Cdq(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	Cdq(l,mid);
	Cdq(mid+1,r);
	sort(a+l,a+mid+1,cMp);
	sort(a+mid+1,a+r+1,cMp);
	int k=l;
	for(int i=mid+1;i<=r;i++){
		while(k<=mid&&a[k].b<=a[i].b)
			Ta.Change(a[k].c,a[k].w),k++;
		a[i].ans+=Ta.Ask(a[i].c);
	}
	for(int i=l;i<k;i++)
		Ta.Change(a[i].c,-a[i].w);
	return;
}
int main()
{
	scanf("%d%d",&m,&k);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&b[i].a,&b[i].b,&b[i].c);
	sort(b+1,b+1+m,Cmp);
	for(int i=1,c=0;i<=m;i++){
		c++;
		if(b[i].a!=b[i+1].a||b[i].b!=b[i+1].b||b[i].c!=b[i+1].c)
			a[++n]=b[i],a[n].w=c,c=0;
	}
	Cdq(1,n);
	for(int i=1;i<=n;i++)
		ask[a[i].ans+a[i].w-1]+=a[i].w;
	for(int i=0;i<m;i++)
		printf("%d\n",ask[i]);
}