CDQ分治
【模板】三维偏序 —— bzoj3262
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+5,M=2e5+5; 4 int n,k,cnt,c[M],ans[N]; 5 struct node {int x,y,z,w,k;}a[N],b[N]; 6 inline int read() { 7 int x=0; char c=getchar(); 8 while(c<'0'||c>'9') c=getchar(); 9 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 10 return x; 11 } 12 13 int lowbit(int x) {return x&(-x);} 14 void update(int i,int x) { 15 for(;i<=k;i+=lowbit(i)) c[i]+=x; 16 } 17 int query(int i) { 18 int h=0; 19 for(;i;i-=lowbit(i)) h+=c[i]; 20 return h; 21 } 22 23 bool cmp1(node x1,node x2) { 24 if(x1.x==x2.x) { 25 if(x1.y==x2.y) return x1.z<x2.z; 26 return x1.y<x2.y; 27 } return x1.x<x2.x; 28 } 29 bool cmp2(node x1,node x2) {return x1.y<x2.y;} 30 31 void CDQ(int l,int r) { 32 if(l==r) return ; 33 int Mid=(l+r)>>1; 34 CDQ(l,Mid); CDQ(Mid+1,r); 35 sort(a+l,a+Mid+1,cmp2); sort(a+Mid+1,a+r+1,cmp2); 36 int j=l; 37 for(int i=Mid+1;i<=r;i++) { 38 while(j<=Mid&&a[j].y<=a[i].y) 39 update(a[j].z,a[j].w),j++; 40 a[i].k+=query(a[i].z); 41 } 42 for(int i=l;i<j;i++) update(a[i].z,-a[i].w); 43 } 44 45 int main() { 46 n=read(),k=read(); 47 for(int i=1;i<=n;i++) 48 b[i].x=read(),b[i].y=read(),b[i].z=read(); 49 sort(b+1,b+n+1,cmp1); int t=0; 50 for(int i=1;i<=n;i++) { 51 t++; 52 if(b[i].x^b[i+1].x||b[i].y^b[i+1].y||b[i].z^b[i+1].z) 53 a[++cnt]=b[i],a[cnt].w=t,t=0; 54 } 55 CDQ(1,cnt); 56 for(int i=1;i<=cnt;i++) 57 ans[a[i].k+a[i].w]+=a[i].w; 58 for(int i=1;i<=n;i++) printf("%d ",ans[i]); 59 return 0; 60 }