1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<cstring> 5 #include<iostream> 6 using namespace std; 7  8 const int D=3e6; 9 char in[D],*I=in,out[D],*O=out;10 11 inline int gint(){12     int x=0;for(;*I<48||*I>57;++I);13     for(;*I>47&&*I<58;++I)x=10*x+*I-48;14     return x;15 }16 17 inline void print(int x){18     char tmp[10],*t=tmp;19     if(!x)*t++=48;20     for(;x;x/=10)*t++=x%10+48;21     for(;t--!=tmp;*O++=*t);22     *O++=‘\n‘;23 }24 25 const int Maxn=100000 + 10;26 int C[Maxn*2],ans[Maxn],N,K,n=0;27 struct Node{28     int a,b,c,s,ans;29     inline bool operator==(const Node&rhs)const{30         return a==rhs.a&&b==rhs.b&&c==rhs.c;31     }32     inline bool operator!=(const Node&rhs)const{33         return !(*this==rhs);34     }35     void init(){a=gint(),b=gint(),c=gint();}36 }p[Maxn],q[Maxn];37 38 inline void Add(int x,const int&y){39     for(;0<x&&x<=K;x+=x&-x)C[x]+=y;40 }41 inline int Query(int x){42     int ret=0;43     for(;0<x&&x<=K;x-=x&-x)ret+=C[x];44     return ret;45 }46 inline bool cmp1(const Node&x,const Node&y){47     if(x.a!=y.a)return x.a<y.a;48     if(x.b!=y.b)return x.b<y.b;49     return x.c<y.c;50 }51 inline bool cmp2(const Node&x,const Node&y){52     if(x.b!=y.b)return x.b<y.b;53     return x.c<y.c; 54 }55 void CDQ(int l,int r){56     if(l==r)return;57     int mid=(l+r)>>1;58     CDQ(l,mid);CDQ(mid+1,r);59     60     int i=l;61     for(int j=mid+1;j<=r;j++){62         for(;i<=mid&&p[i].b<=p[j].b;i++)63             Add(p[i].c,p[i].s);64         p[j].ans+=Query(p[j].c);65     }66     for(int j=l;j<i;j++)Add(p[j].c,-p[j].s);67     merge(p+l,p+mid+1,p+mid+1,p+r+1,q,cmp2);68     memcpy(p+l,q,sizeof(p[0])*(r-l+1));69 }70 void init(){71     N=gint(),K=gint();72     for(int i=1;i<=N;i++)q[i].init();73     sort(q+1,q+N+1,cmp1);74     for(int cnt=1,i=1;i<=N;i++,cnt++){75         if(q[i]!=q[i+1]){p[++n]=q[i];p[n].s=cnt;cnt=0;}76     }77 }78 int main(){79     freopen("in.txt","r",stdin);80     freopen("out.txt","w",stdout);81     82     fread(I,1,D,stdin);83     84     init();85     CDQ(1,n);86     87     for(int i=1;i<=n;i++)ans[p[i].ans+p[i].s-1]+=p[i].s;88     for(int i=0;i<N;i++)print(ans[i]);89     90     *--O=0;91     92     return puts(out),0;93 }