哇塞大佬好厉害
据说正解是一维排序，二维CDQ，三维树状数组的……
然而大佬硬是二维三维都用了CDQ……
而且莫名好写……太暴力了……
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 using std::sort; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 inline int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 char sr[1<<21],z[20];int C=-1,Z; 19 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 20 inline void print(int x){ 21 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 22 while(z[++Z]=x%10+48,x/=10); 23 while(sr[++C]=z[Z],--Z);sr[++C]=' '; 24 } 25 const int N=100005; 26 int n,k,ans[N],d[N]; 27 struct node{ 28 int x,y,z; 29 bool b;int *ans; 30 inline void get(){ 31 x=read(),y=read(),z=read(); 32 } 33 inline bool operator ==(const node &a)const 34 {return x==a.x&&y==a.y&&z==a.z;} 35 }a[N],b[N],c[N]; 36 inline bool cmp(const node &a,const node &b){ 37 return a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.z<b.z); 38 } 39 void merge2(int l,int r){ 40 if(l==r) return; 41 int mid=(l+r)>>1; 42 merge2(l,mid),merge2(mid+1,r); 43 int i=l,j=l,k=mid+1,cnt=0; 44 while(j<=mid&&k<=r){ 45 if(b[j].z<=b[k].z){ 46 c[i]=b[j++],cnt+=c[i].b; 47 } 48 else{ 49 c[i]=b[k++]; 50 if(!c[i].b) *c[i].ans+=cnt; 51 } 52 ++i; 53 } 54 while(j<=mid) 55 c[i]=b[j++],++i; 56 while(k<=r){ 57 c[i]=b[k++]; 58 if(!c[i].b) *c[i].ans+=cnt; 59 ++i; 60 } 61 for(int i=l;i<=r;++i) b[i]=c[i]; 62 } 63 void merge1(int l,int r){ 64 if(l==r) return; 65 int mid=(l+r)>>1; 66 merge1(l,mid),merge1(mid+1,r); 67 int i=l,j=l,k=mid+1; 68 while(j<=mid&&k<=r){ 69 if(a[j].y<=a[k].y){ 70 b[i]=a[j++],b[i].b=1; 71 } 72 else{ 73 b[i]=a[k++],b[i].b=0; 74 } 75 ++i; 76 } 77 while(j<=mid) 78 b[i]=a[j++],b[i].b=1,++i; 79 while(k<=r) 80 b[i]=a[k++],b[i].b=0,++i; 81 for(int i=l;i<=r;++i) a[i]=b[i]; 82 merge2(l,r); 83 } 84 int main(){ 85 //freopen("testdata.in","r",stdin); 86 n=read(),k=read(); 87 for(int i=1;i<=n;++i) 88 a[i].get(),a[i].ans=&ans[i],ans[i]=0; 89 sort(a+1,a+n+1,cmp); 90 for(int i=n-1;i;--i) 91 if(a[i]==a[i+1]) *a[i].ans=*a[i+1].ans+1; 92 merge1(1,n); 93 for(int i=1;i<=n;++i) ++d[ans[i]]; 94 for(int i=0;i<n;++i) print(d[i]); 95 Ot(); 96 return 0; 97 }