BZOJ3262: 陌上花开【CDQ三维偏序】

3262: 陌上花开

一道求三维偏序的裸题。

第一维排序。

第二维二路归并，此时我们已经保证了左边一半的元素都小于等于右边一半。

第三维树状数组求逆序对。

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100005;
int n,m,tot;
struct xcw{
	int x,y,z,w,s;
	bool operator ==(const xcw b)const{return x==b.x&&y==b.y&&z==b.z;}
	bool operator <(const xcw b)const{return x<b.x||(x==b.x&&y<b.y)||(x==b.x&&y==b.y&&z<b.z);}
}a[MAXN],t[MAXN];
int F[MAXN],Ans[MAXN];
void Add(int x,int p){for(;x<=m;x+=x&-x) F[x]+=p;}
int Get(int x){int Sum=0;for(;x;x-=x&-x) Sum+=F[x];return Sum;}
void CDQ(int L,int R){
	if(L==R) return;int mid=(R+L)>>1;
	CDQ(L,mid),CDQ(mid+1,R);
	int i=L,j=mid+1,p=L-1;
	while(i<=mid||j<=R){
		if((i<=mid&&a[i].y<=a[j].y)||j>R) Add(a[i].z,a[i].w),t[++p]=a[i++];
		else a[j].s+=Get(a[j].z),t[++p]=a[j++];
	}
	for(int i=L;i<=mid;i++) Add(a[i].z,-a[i].w);
	for(int i=L;i<=R;i++) a[i]=t[i];
}
#include<cctype>
int read(){
	int ret=0;char ch=getchar();bool f=1;
	for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
	for(; isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;
	return f?ret:-ret;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=(xcw){read(),read(),read(),0,0};
	sort(a+1,a+1+n);
	for(int i=1,j=1;i<=n;i=j){
		for(j=i+1;j<=n&&a[i]==a[j];j++);
		a[++tot]=a[i];a[tot].w=j-i;
	}
	CDQ(1,tot);
	for(int i=1;i<=tot;i++) Ans[a[i].s+a[i].w-1]+=a[i].w;
	for(int i=0;i<n;i++) printf("%d\n",Ans[i]);
	return 0;
}