代码

typedef unsigned u32;typedef unsigned long U;enum{N=10000005,R=4096};typedef struct{u32 x,y,id,z;}P;static P a[N],b[N];static u32 c[R],p[R],bg[R+1],*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 x=(q->x>>bit)&4095,z=0;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],bb[R+1];bb[0]=l;for(int q=0;q<R;++q)ps[q]=bb[q],bb[q+1]=bb[q]+ct[q];for(int i=l;i<r;++i){P q=s[i];d[ps[(q.x>>bit)&4095]++]=q;}for(int q=0;q<R;++q)if(bb[q]<bb[q+1])go(d,s,bb[q],bb[q+1],bit-12);}
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]>>12];u32 z=0;bg[0]=0;for(int q=0;q<R;++q){u32 t=c[q];p[q]=z;z+=t;bg[q+1]=z;}for(int i=0;i<n;++i){u32 yy=y[i];a[p[yy>>12]++]=(P){x[i],yy,(u32)i,0};}
 for(int h=0;h<R;++h){int l=bg[h],r=bg[h+1];if(l==r)continue;__builtin_memset(c,0,sizeof c);for(int i=l;i<r;++i)++c[a[i].y&4095];u32 z=l;for(int q=0;q<R;++q){u32 t=c[q];p[q]=z;z+=t;}for(int i=l;i<r;++i){P q=a[i];b[p[q.y&4095]++]=q;}}
 for(int f=0;f<n;){int e=f+1;while(e<n&&b[e].y==b[f].y)++e;for(int i=f+1;i<e;++i){P q=b[i];int j=i;while(j>f&&b[j-1].x>q.x)b[j]=b[j-1],--j;b[j]=q;}for(int q=f;q<e;){int t=q+1;while(t<e&&b[t].x==b[q].x)++t;u32 w=q-f;for(int i=q;i<t;++i)b[i].z=0-w;q=t;}f=e;}go(b,a,0,n,12);}
#ifndef LOCAL
static char**v;static U cc;U getauxval(U k){char**p_=v+cc+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){cc=ac;v=av;e(ac,av,0);__asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall":::"rax","rdi","rcx","r11","memory");__builtin_unreachable();}
#endif

评测结果