夏晓光(loveJY)的博客

重糊带师

我们之前的做法是cdq套cdq,但是这个做法复杂度虽然正确常数爆炸爆炸qwq

所以我们这里用树状数组写了一遍

首先我们要保证用a第一维排序,然后b和c是第二第三关键字去排序

然后cdq归并排序去保证b哪一位左边小于右边

再用树状数组保证左边小于右边

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid ((l+r)>>1)
using std::sort;
const int MAXN=2e5+7;
int n,qwq,tag[MAXN];
struct NODE {
	int a,b,c,ans,cnt;
	bool operator<(const NODE &x)const {
//		return a<x.a;
		if(a==x.a) {
			if(b==x.b)return c<x.c;
			else return b<x.b;
		} else return a<x.a;
	}
} node[MAXN],b[MAXN],que[MAXN],a[MAXN];

namespace seg {
#define lowbit(x) (x&(-x))
	int tr[MAXN];
	inline void add(int x,int val) {
		for(; x<MAXN; x+=lowbit(x)) {
			tr[x]+=val;
		}
	}
	inline int qry(int x) {
		int ret=0;
		for(; x; x-=lowbit(x)) {
			ret+=tr[x];
		}
		return ret;
	}
}
using namespace seg;

inline void solve(int l,int r) {
	if(l==r)return ;
	solve(l,mid);
	solve(mid+1,r);
//	sort(node+l,node+mid+1,cmp);
//	sort(node+mid+1,node+r,cmp);
//	printf("%d %d %d\n",l,mid,r);
	int cnt=0;
	for(int i=l,j=l,k=mid+1; i<=r; ++i) {
		if((k>r||node[j].b<=node[k].b)&&(j<=mid)) {
//			printf("?%d %d %d %d\n",node[j].id,node[j].a,node[j].b,node[j].c);
			add(node[j].c,node[j].cnt);
			que[++cnt]=node[j];
			b[i]=node[j];
			++j;

		} else {
//			printf("!%d %d %d %d->",node[k].id,node[k].a,node[k].b,node[k].c);
			int tmp=qry(node[k].c);
			node[k].ans+=tmp;
//			printf("%d\n",tmp);
			b[i]=node[k];
			++k;
		}
	}
//	puts("QWQ");
	for(int i=1; i<=cnt; ++i) {
//		printf("%dQWQ %d ",que[i].c,que[i].cnt);
		add(que[i].c,-que[i].cnt);
	}
//	printf("\n\n");
	for(int i=l; i<=r; ++i) {
//		if(i<=tmp) {
//		printf(")%d %d %d %d\n",node[i].id,node[i].a,node[i].b,node[i].c);
//			add(node[i].c,-1);
//		}
		node[i]=b[i];
	}
	return ;
}

int main() {
	scanf("%d%d",&n,&qwq);
	for(int i=1; i<=n; ++i) {
		scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
//		a[i].id=i;
	}
	sort(a+1,a+n+1);
	int top=0;
	int rc=0;
	for(int i=1; i<=n; ++i) {
		top++;
		if(a[i+1].a!=a[i].a||a[i+1].b!=a[i].b||a[i+1].c!=a[i].c) {
			node[++rc]=a[i];
			node[rc].cnt=top;
			top=0;
		}
	}
	solve(1,rc);
	for(int i=1; i<=rc; ++i) {
		tag[node[i].ans+node[i].cnt-1]+=node[i].cnt;
//		printf("%d\n",ans[i]);
	}
	for(int i=0; i<n; ++i) {
		printf("%d\n",tag[i]);
	}
	return 0;
}