求助qwq
查看原帖
求助qwq
701408
lao_wang楼主2024/3/5 15:20

新手刚开始学习些cdq有没有大佬能帮忙看看是哪里错了,感谢

#include<bits/stdc++.h>
#define int long long
using namespace std ;
struct node{
	int a , b , c , i , w ;
}a[123456],tempp[123456];
int n , k , ans[123456] , h=0 , sum=0 , t[123456] , tr[9923456] ;
bool cmp(node a,node b){
	return a.a<b.a+(a.b==b.b?a.c<b.c:a.b<b.b) ;
}
void gai(long long x,long long a) {
	while(x<=300000) {
		tr[x] += a ;
		x += (x&-x) ;
	}
}
long long ask(long long i) {
	long long sum=0 ;
	while(i>0) {
		sum += tr[i] ;
		i -= (i&-i) ;
	}
	return sum ;
}
void cdq(int l,int r){
	if(l>=r) return ;
	int mid=(l+r)>>1 , i=l , j=mid+1 , tot=0 ;
	cdq(l,mid) ;
	cdq(mid+1,r) ;
	while(i<=mid&&j<=r){
		if(a[i].b<=a[j].b){tempp[++tot] = a[i] ; gai(a[i].c,a[i].w) ;i++;}
		else{tempp[++tot] = a[j] ; t[a[j].i] += ask(a[j].c) ;j++;}
	}
	while(j<=r) tempp[++tot] = a[j] , t[a[j].i] += ask(a[j].c) , j++ ;
	while(i<=mid) tempp[++tot] = a[i] , gai(a[i].c,a[i].w) , i++ ;
	for(i=l;i<=mid;i++) gai(a[i].c,-a[i].w) ; 
	for(i=l,j=1;j<=tot;i++,j++) a[i] = tempp[j] ;
}
signed main(){
	cin >> n >> k ;
	for(int i=1;i<=n;a[i].i=i,i++){
		scanf("%lld%lld%lld",&a[i].a,&a[i].b,&a[i].c) ;
		a[i].w = 1;
	}
	sort(a+1,a+1+n,cmp) ;
	cdq(1,n) ;
	for(int i=1;i<=n;i++){
		ans[t[i]]++ ;
	}
	for(int i=0;i<n;i++)
		printf("%lld\n",ans[i]) ;
	return 0 ;
}
2024/3/5 15:20
加载中...