新手刚开始学习些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 ;
}