代码

typedef unsigned u32;typedef unsigned long U;enum{MAXN=10000005,R=4096,SMALL=12};
typedef struct{u32 z,y,id;}P;static P a[MAXN],b[MAXN];static u32 cnt[R],pos[R],*ans;
static __attribute__((noinline))void go(P*s,P*d,int l,int r,int bit){int n=r-l;if(n<=SMALL){for(int j=l;j<r;++j){P p=s[j];u32 z=0;for(int i=l;i<j;++i)z+=s[i].y<p.y;ans[p.id]=p.z+z;}return;}u32 fen[R+1]={0},ct[R]={0};for(int i=l;i<r;++i){P p=s[i];u32 q=(p.y>>bit)&(R-1),z=0;for(u32 k=q;k;k&=k-1)z+=fen[k];p.z+=z;s[i].z=p.z;++ct[q];for(u32 k=q+1;k<=R;k+=k&-k)++fen[k];}if(!bit){for(int i=l;i<r;++i)ans[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 p=s[i];d[ps[(p.y>>bit)&(R-1)]++]=p;}for(int q=0;q<R;++q)if(bg[q]<bg[q+1])go(d,s,bg[q],bg[q+1],bit-12);}
void count_2d(int n,const u32*x,const u32*y,u32*out){ans=out;
#ifdef LOCAL
 __builtin_memset(cnt,0,sizeof cnt);
#endif
 for(int i=0;i<n;++i)++cnt[x[i]&4095];u32 s=0;for(int q=0;q<R;++q){u32 c=cnt[q];pos[q]=s;s+=c;}for(int i=0;i<n;++i){u32 xv=x[i];a[pos[xv&4095]++]=(P){xv,y[i],(u32)i};}
 __builtin_memset(cnt,0,sizeof cnt);for(int i=0;i<n;++i)++cnt[a[i].z>>12];s=0;for(int q=0;q<R;++q){u32 c=cnt[q];pos[q]=s;s+=c;}for(int i=0;i<n;++i){P p=a[i];b[pos[p.z>>12]++]=p;}
 for(int f=0;f<n;){int e=f+1;while(e<n&&b[e].z==b[f].z)++e;for(int i=f+1;i<e;++i){P p=b[i];int j=i;while(j>f&&b[j-1].y>p.y)b[j]=b[j-1],--j;b[j]=p;}for(int q=f;q<e;){int t=q+1;while(t<e&&b[t].y==b[q].y)++t;u32 z=q-f;for(int i=q;i<t;++i)b[i].z=0-z;q=t;}f=e;}
 go(b,a,0,n,12);
}
#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

评测结果