//第一维排序，第二维cdq分治，第三维树状数组 #include<bits/stdc++.h> using namespace std; #define lowbit(x) (x&-(x)) const int maxn = 200006; int a[200009],ans[200009]; struct flower { int x,y,z,sum,cnt; bool operator==(const flower &p)const { return x==p.x&&y==p.y&&z==p.z; } } p[100009]; bool cmp1(flower a, flower b) { if(a.x != b.x) return a.x < b.x; if(a.y!=b.y) return a.y<b.y; return a.z < b.z; } bool cmp2(flower a, flower b) { return a.y < b.y; } void add(int x, int y) { for(int i = x; i<=maxn; i+=lowbit(i)) { a[i] += y; } } int sum(int x) { int ans = 0; for(int i = x; i; i-=lowbit(i)) { ans +=a[i]; } return ans; } void cdq(int l,int r) { if(l == r) return; int mid = ((l+r)>>1); cdq(l,mid); cdq(mid+1,r); //左半部分，右半部分的问题已解决 sort(p+l,p+mid+1,cmp2); sort(p+mid+1,p+r+1,cmp2); int i,j = l; //解决左半部分对右半部分的贡献（右半部分对左半部分无贡献） for(i = mid+1; i<= r; i++)//递归右半部分 { for(; j<=mid&&p[j].y<=p[i].y; j++)//左半部分x，y值小于右半部分的，树状数组记录 { add(p[j].z,p[j].cnt); } p[i].sum += sum(p[i].z); } for(i = l; i<j; i++)//把树状数组清空 { add(p[i].z,-p[i].cnt); } } int main() { int k,i,j,m,n; scanf("%d %d",&n, &m); for(i = 1; i <= n; i++) { scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z); p[i].sum = p[i].cnt = 0; } memset(a,0,sizeof(a)); sort(p+1,p+n+1,cmp1); k = 0; for(i = 1; i <= n; i++)//去重 { for(j = i; p[i]==p[j]&&j<=n; j++) { p[i].cnt ++;//记录这个元素的个数 } p[++k] = p[i]; i = j-1; } cdq(1,k); memset(ans,0,sizeof(ans)); for(i = 1; i<= k; i++) { ans[p[i].sum+p[i].cnt-1] += p[i].cnt; } for(i = 0; i< n; i++) { printf("%d\n",ans[i]); } return 0; }
