333

视频链接：

#include <algorithm>
#include <cstdio>
using namespace std;

#define lowb(x) x&-x
const int N=1e5+10, K=2e5+10;
int n,k,m,t;
int res[N],s[K];

struct E{
  int a,b,c,cnt,res;
  bool operator!=(E other){
    if(a!=other.a) return true;
    if(b!=other.b) return true;
    if(c!=other.c) return true;
    return false;
  }
}e[N],ue[N];

void change(int x,int k){ //向后修
  while(x<=K) s[x]+=k, x+=lowb(x);
}
int query(int x){ //向前查
  int t=0;
  while(x) t+=s[x], x-=lowb(x);
  return t;
}
bool cmp1(E x,E y){
  if(x.a!=y.a) return x.a<y.a;
  if(x.b!=y.b) return x.b<y.b;
  return x.c<y.c;
}
bool cmp2(E x,E y){
  if(x.b!=y.b) return x.b<y.b;
  return x.c<y.c;
}
void CDQ(int l,int r){
  if(l==r) return;
  int mid=(l+r)/2;
  CDQ(l,mid);
  CDQ(mid+1,r);
  sort(ue+l,ue+mid+1,cmp2);
  sort(ue+mid+1,ue+r+1,cmp2);
  
  int i=l,j=mid+1;
  while(j<=r){
    while(i<=mid && ue[i].b<=ue[j].b){
      change(ue[i].c,ue[i].cnt);
      i++;
    }
    ue[j].res+=query(ue[j].c);
    j++;
  }
  for(int k=l;k<i;k++) 
    change(ue[k].c,-ue[k].cnt);
}
int main(){
  scanf("%d%d",&n,&k);
  for(int i=1;i<=n;i++) 
    scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
  sort(e+1,e+n+1,cmp1);
  for(int i=1;i<=n;i++){
    t++;
    if(e[i]!=e[i+1]){
      m++;
      ue[m].a=e[i].a;
      ue[m].b=e[i].b;
      ue[m].c=e[i].c;
      ue[m].cnt=t;
      t=0;
    }
  }
  CDQ(1,m);
  for(int i=1;i<=m;i++) 
    res[ue[i].res+ue[i].cnt-1]+=ue[i].cnt;
  for(int i=0;i<n;i++) printf("%d\n",res[i]);
}