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

ref1

ref2

ref3

ref4
#include <algorithm>

#include <iostream>

#include <cstdio>

using namespace std;

int n, k, c[200005], cnt[200005];

struct Node{

	int x, y, z, idx, ans;

	bool operator==(const Node &u)const{

		return x==u.x && y==u.y && z==u.z;

	}

}a[100005], qwq, b[100005];

bool cmp(const Node &u, const Node &v){

	if(u.x!=v.x)	return u.x<v.x;

	else if(u.y!=v.y)	return u.y<v.y;

	else	return u.z<v.z;

}

int lb(int x){

	return x & -x;

}

void add(int x, int v){

	for(; x<=k; x+=lb(x))

		c[x] += v;

}

int query(int x){

	int re=0;

	for(; x; x-=lb(x))

		re += c[x];

	return re;

}

void cdq(int l, int r){

	if(l==r)	return ;

	int mid=(l+r)>>1;

	cdq(l, mid); cdq(mid+1, r);

	int jj=l, kk=mid+1;

	for(int i=l; i<=r; i++)

		if(jj<=mid && (kk>r || a[jj].y<=a[kk].y))	b[i] = a[jj++];

		else	b[i] = a[kk++];

	for(int i=l; i<=r; i++){

		a[i] = b[i];

		if(a[i].idx<=mid)	add(a[i].z, 1);

		else	a[i].ans += query(a[i].z);

	}

	for(int i=l; i<=r; i++)

		if(a[i].idx<=mid)

			add(a[i].z, -1);

}

int main(){

	cin>>n>>k;

	for(int i=1; i<=n; i++)

		scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);

	sort(a+1, a+1+n, cmp);

	int orzwys1996=1;

	for(int i=n; i>=1; i--){

		if(a[i]==qwq){

			a[i].ans += orzwys1996;

			orzwys1996++;

		}

		else{

			qwq = a[i];

			orzwys1996 = 1;

		}

		a[i].idx = i;

	}

	cdq(1, n);

	for(int i=1; i<=n; i++)

		cnt[a[i].ans]++;

	for(int i=0; i<n; i++)

		printf("%d\n", cnt[i]);

	return 0;

}
巴特西

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

最新文章

热门文章
