代码

typedef unsigned u32;typedef unsigned long U;enum{N=10000005,R=256};typedef struct{u32 x,y,id,z;}P;static P a[N],b[N];static u32 c[R],p[R],*o;
static __attribute__((noinline))void go(P*s,P*d,int l,int r,int bit){u32 f[R+1]={0},ct[R]={0};for(int i=l;i<r;++i){P*q=s+i;u32 z=0,x=(q->x>>bit)&255;for(u32 k=x;k;k&=k-1)z+=f[k];q->z+=z;++ct[x];for(u32 k=x+1;k<=R;k+=k&-k)++f[k];}if(!bit){for(int i=l;i<r;++i)o[s[i].id]=s[i].z;return;}int ps[R],bg[R+1];bg[0]=l;for(int q=0;q<R;++q)ps[q]=bg[q],bg[q+1]=bg[q]+ct[q];for(int i=l;i<r;++i){P q=s[i];d[ps[(q.x>>bit)&255]++]=q;}for(int q=0;q<R;++q)if(bg[q]<bg[q+1])go(d,s,bg[q],bg[q+1],bit-8);}
void count_2d(int n,const u32*x,const u32*y,u32*out){o=out;
#ifdef LOCAL
 __builtin_memset(c,0,sizeof c);
#endif
 for(int i=0;i<n;++i)++c[y[i]&255];u32 z=0;for(int q=0;q<R;++q){u32 t=c[q];p[q]=z;z+=t;}for(int i=0;i<n;++i){u32 yy=y[i];a[p[yy&255]++]=(P){x[i],yy,(u32)i,0};}
 for(int bit=8;bit<=16;bit+=8){__builtin_memset(c,0,sizeof c);P*s=bit==8?a:b,*d=bit==8?b:a;for(int i=0;i<n;++i)++c[(s[i].y>>bit)&255];z=0;for(int q=0;q<R;++q){u32 t=c[q];p[q]=z;z+=t;}for(int i=0;i<n;++i){P q=s[i];d[p[(q.y>>bit)&255]++]=q;}}
 for(int f=0;f<n;){int e=f+1;while(e<n&&a[e].y==a[f].y)++e;for(int i=f+1;i<e;++i){P q=a[i];int j=i;while(j>f&&a[j-1].x>q.x)a[j]=a[j-1],--j;a[j]=q;}for(int q=f;q<e;){int t=q+1;while(t<e&&a[t].x==a[q].x)++t;u32 w=q-f;for(int i=q;i<t;++i)a[i].z=0-w;q=t;}f=e;}go(a,b,0,n,16);}
#ifndef LOCAL
static char**v;static U c_;U getauxval(U k){char**p_=v+c_+1;while(*p_)++p_;U*q=(U*)(p_+1);while(*q){if(*q==k)return q[1];q+=2;}return 0;}__attribute__((noreturn))void __libc_start_main(int(*e)(int,char**,char**),int ac,char**av){c_=ac;v=av;e(ac,av,0);__asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall":::"rax","rdi","rcx","r11","memory");__builtin_unreachable();}
#endif

评测结果