一维排序； 二维CDQ； 三维BIT。 LuoguP3810 先上代码，代码还是蛮长的 事实上可以免去
//1D ............ cdq(1,num);中间的............ 然而有重复。。。
struct point { int a,b,c,cnt,ans; }g[100010]; int n,m,ans[100010],bit[10000010],num; bool cmp2(point x,point y) { if(x.b==y.b) rt x.c<y.c; rt x.b<y.b; } bool cmp1(point x,point y) { if(x.a==y.a) rt cmp2(x,y); rt x.a<y.a; } void add(int x,int y) { while(x<=m) { bit[x]+=y; x+=x&(-x); } } int query(int x) { int r=0; while(x) { r+=bit[x]; x-=x&(-x); } rt r; } void cdq(int l,int r) { if(l==r) rt; int mid=(l+r)>>1; cdq(l,mid); cdq(mid+1,r); sort(g+l,g+mid+1,cmp2); sort(g+mid+1,g+r+1,cmp2);//2D int t1=l,t2=mid+1; while(t2<=r) { while(t1<=mid&&g[t1].b<=g[t2].b) { add(g[t1].c,g[t1].cnt); t1++; } g[t2].ans+=query(g[t2].c); t2++; } fr(i,l,t1-1) add(g[i].c,-g[i].cnt);//3D } int main() { n=read(); m=read(); fr(i,1,n) g[i].a=read(),g[i].b=read(),g[i].c=read(),g[i].cnt=1; sort(g+1,g+n+1,cmp1);//1D fr(i,1,n) { int k=i+1; while(g[i].a==g[k].a&&g[i].b==g[k].b&&g[i].c==g[k].c) k++; num++; k--; g[i].cnt+=k-i; g[num]=g[i]; i=k; } cdq(1,num); fr(i,1,num) ans[g[i].ans+g[i].cnt-1]+=g[i].cnt; fr(i,0,n-1) printf("%d\n",ans[i]); rt 0; }