代码

typedef unsigned u32;typedef unsigned long U;
enum{N=10000005,LY=16384,HY=611,LX=8192,HX=1221};typedef struct{u32 x,y,id,z;}P;
static P a[N],b[N];static u32 hc[HY],hp[HY],yb[HY+1],*o;
static __attribute__((target("avx2,bmi,bmi2,popcnt"),noinline))void low(P*s,int l,int r){u32 f[LX]={0};for(int i=l;i<r;++i){P*q=s+i;u32 x=q->x&(LX-1),z=0;for(u32 k=x;k;k&=k-1)z+=f[k];q->z+=z;for(u32 k=x+1;k<LX;k+=k&-k)++f[k];o[q->id]=q->z;}}
static __attribute__((target("avx2,bmi,bmi2,popcnt"),noinline))void solve(P*s,P*d,int n){u32 f[HX]={0},ct[HX]={0};for(int i=0;i<n;++i){P*q=s+i;u32 x=q->x>>13,z=0;for(u32 k=x;k;k&=k-1)z+=f[k];q->z+=z;++ct[x];for(u32 k=x+1;k<HX;k+=k&-k)++f[k];}int ps[HX],bg[HX+1];bg[0]=0;for(int q=0;q<HX;++q)ps[q]=bg[q],bg[q+1]=bg[q]+ct[q];for(int i=0;i<n;++i){P q=s[i];d[ps[q.x>>13]++]=q;}for(int q=0;q<HX;++q)if(bg[q]<bg[q+1])low(d,bg[q],bg[q+1]);}
__attribute__((target("avx2,bmi,bmi2,popcnt")))void count_2d(int n,const u32*x,const u32*y,u32*out){o=out;
#ifdef LOCAL
 __builtin_memset(hc,0,sizeof hc);
#endif
 for(int i=0;i<n;++i)++hc[y[i]>>14];u32 z=0;yb[0]=0;for(int q=0;q<HY;++q){u32 t=hc[q];hp[q]=z;z+=t;yb[q+1]=z;}for(int i=0;i<n;++i){u32 yy=y[i],k=hp[yy>>14]++;a[k].x=x[i];a[k].y=yy;a[k].id=i;}for(int h=0;h<HY;++h){int l=yb[h],r=yb[h+1];if(l==r)continue;u32 c[LY]={0},p[LY];for(int i=l;i<r;++i)++c[a[i].y&(LY-1)];z=l;for(int q=0;q<LY;++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&(LY-1)]++]=q;}for(int f=l;f<r;){int e=f+1;while(e<r&&b[e].y==b[f].y)++e;for(int i=f;i<e;++i){u32 w=0;for(int j=f;j<i;++j)w-=b[j].x<b[i].x;b[i].z=w;}f=e;}}solve(b,a,n);}
#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

评测结果