代码

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

评测结果