1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<vector> 5 using namespace std; 6 struct Point{int x,y,z,num;void Read(){scanf("%d%d%d",&x,&y,&z);}}p[100002]; 7 bool operator < (const Point &a,const Point &b){return a.x<b.x;} 8 bool cmp (const Point &a,const Point &b){return a.y<b.y;} 9 vector<int>b[400];10 vector<Point>a[400];11 int n,rank[100001],m,head,maxv[400],sum;12 void makeblock()13 {14     int sz=(int)sqrt((double)n*(log((double)n)/log(2.0))); if(!sz) sz=1;15     for(sum=1;sum*sz<n;sum++)16       {17         int R=sum*sz;18         for(int i=(sum-1)*sz+1;i<=R;i++) p[i].num=sum;19         maxv[sum]=p[R].y;20       }21     for(int i=(sum-1)*sz+1;i<=n;i++) p[i].num=sum;22     maxv[sum]=p[n].y;23 }24 void insert(const Point &U)25 {26     b[U.num].insert(upper_bound(b[U.num].begin(),b[U.num].end(),U.z),U.z);27     a[U.num].push_back(U);28 }29 int query(const Point &U)30 {31     int cnt=0,i;32     for(i=1;i<=sum && maxv[i]<=U.y;++i)33       cnt+=upper_bound(b[i].begin(),b[i].end(),U.z)-b[i].begin();34     for(vector<Point>::iterator it=a[i].begin();it!=a[i].end();++it)35       if((*it).z<=U.z&&(*it).y<=U.y) ++cnt;36     return cnt;37 }38 int main()39 {40     scanf("%d%d",&n,&m);41     for(int i=1;i<=n;i++) p[i].Read();42     sort(p+1,p+n+1,cmp); makeblock();43     sort(p+1,p+n+1);44     for(int i=1;i<=n;i++)45       {46           if(p[i].x!=p[i-1].x) head=i;47         if(p[i].x!=p[i+1].x)48           {49               for(int j=head;j<=i;j++) insert(p[j]);50               for(int j=head;j<=i;j++) ++rank[query(p[j])-1];51           }52       }53     for(int i=0;i<n;i++) printf("%d\n",rank[i]);54     return 0;55 }