裸的三维偏序。 对x坐标排序，y、z坐标分块。复杂度O(n*sqrt(n*log(n)))。代码很短。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          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[400];10 vector

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

::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