代码

// 5D dominance CDQ: +1-offset unsigned coords, bottom-up ping-pong, u64 packing.
// Structure: cdq0(merge c1) -> cdq1(merge c2) -> cdq2(merge c3) -> cdq3(merge c4) -> cdq4(counter)
#include <cstring>
typedef unsigned u32; typedef int i32; typedef unsigned long long u64;
static u32 ans[300000];
static u32 L0[6*600002]; static u32 T0[6*600002];   // key,c1p,c2p,c3p,c4p,meta
static u32 L1[5*600002]; static u32 T1[5*600002];   // c1p,c2p,c3p,c4p,meta
static u32 L2[4*600002]; static u32 T2[4*600002];   // c2p,c3p,c4p,meta
static u64 L3[600002]; static u64 T3[600002];       // c3p | c4p<<19 | meta<<38
static u32 L4[600002];                               // meta (for counter)
static u32 cnt[65536];
#define M19 0x7FFFFu

static void rs0(int m) {
    memset(cnt,0,sizeof(cnt)); for(int i=0;i<m;i++) cnt[L0[6*i] & 0xFFFF]++;
    { u32 s=0; for(int i=0;i<65536;i++){ u32 c=cnt[i]; cnt[i]=s; s+=c; } }
    for(int i=0;i<m;i++){ u32*e=L0+6*i; u32 p=cnt[e[0]&0xFFFF]++; u32*d=T0+6*p; d[0]=e[0];d[1]=e[1];d[2]=e[2];d[3]=e[3];d[4]=e[4];d[5]=e[5]; }
    memset(cnt,0,sizeof(cnt)); for(int i=0;i<m;i++) cnt[T0[6*i]>>16]++;
    { u32 s=0; for(int i=0;i<65536;i++){ u32 c=cnt[i]; cnt[i]=s; s+=c; } }
    for(int i=0;i<m;i++){ u32*e=T0+6*i; u32 p=cnt[e[0]>>16]++; u32*d=L0+6*p; d[0]=e[0];d[1]=e[1];d[2]=e[2];d[3]=e[3];d[4]=e[4];d[5]=e[5]; }
}

static void cdq4(int l,int r){ u32 c=0; for(int i=l;i<r;i++){ u32 m=L4[i]; if(m&1) ans[m>>1]+=c; else c++; } }

// L3: u64 c3p|c4p<<19|meta<<38, merge by c4p (bits 19..37), extract meta to L4 (u32)
static void cdq3(int N) {
    if (N<=1) return;
    u64*src=L3,*dst=T3;
    for(int w=1;w<N;w<<=1){ int cc0=0;
        for(int l=0;l<N;l+=2*w){ int mid=l+w;if(mid>N)mid=N; int r=l+2*w;if(r>N)r=N;
            if(mid>=r){ for(int t=l;t<r;t++) dst[t]=src[t]; continue; }
            int i=l,j=mid,k=l,cc=cc0;
            while(i<mid&&j<r){ u64 ai=src[i],aj=src[j]; int lf=(((ai>>19)&M19)<=((aj>>19)&M19)); u64 s=lf?ai:aj; dst[k]=s; u32 m=(u32)(s>>38); L4[cc]=m; cc+=(lf^(m&1)); i+=lf;j+=1-lf;k++; }
            while(i<mid){ u64 s=src[i]; u32 m=(u32)(s>>38); dst[k]=s; L4[cc]=m; cc+=!(m&1); i++;k++; }
            while(j<r){ u64 s=src[j]; u32 m=(u32)(s>>38); dst[k]=s; L4[cc]=m; cc+=(m&1); j++;k++; }
            cdq4(cc0,cc);
        }
        u64*t=src;src=dst;dst=t;
    }
}

// L2: 4 u32 c2p,c3p,c4p,meta, merge by c3p, extract {c3p,c4p,meta} to L3 u64
static void cdq2(int N) {
    if (N<=1) return;
    u32*src=L2,*dst=T2;
    for(int w=1;w<N;w<<=1){
        for(int l=0;l<N;l+=2*w){ int mid=l+w;if(mid>N)mid=N; int r=l+2*w;if(r>N)r=N;
            if(mid>=r){ for(int t=l;t<r;t++){dst[4*t]=src[4*t];dst[4*t+1]=src[4*t+1];dst[4*t+2]=src[4*t+2];dst[4*t+3]=src[4*t+3];} continue; }
            int i=l,j=mid,k=l,cc=0;
            while(i<mid&&j<r){ u32 a0=src[4*i],a1=src[4*i+1],a2=src[4*i+2],a3=src[4*i+3]; u32 b0=src[4*j],b1=src[4*j+1],b2=src[4*j+2],b3=src[4*j+3]; int lf=(a1<=b1); u32 m=lf?a3:b3; dst[4*k]=lf?a0:b0;dst[4*k+1]=lf?a1:b1;dst[4*k+2]=lf?a2:b2;dst[4*k+3]=m; u32 c3=lf?a1:b1,c4=lf?a2:b2; L3[cc]=(u64)c3|((u64)c4<<19)|((u64)m<<38); cc+=(lf^(m&1)); i+=lf;j+=1-lf;k++; }
            while(i<mid){ u32*e=src+4*i; dst[4*k]=e[0];dst[4*k+1]=e[1];dst[4*k+2]=e[2];dst[4*k+3]=e[3]; L3[cc]=(u64)e[1]|((u64)e[2]<<19)|((u64)e[3]<<38); cc+=!(e[3]&1); i++;k++; }
            while(j<r){ u32*e=src+4*j; dst[4*k]=e[0];dst[4*k+1]=e[1];dst[4*k+2]=e[2];dst[4*k+3]=e[3]; L3[cc]=(u64)e[1]|((u64)e[2]<<19)|((u64)e[3]<<38); cc+=(e[3]&1); j++;k++; }
            cdq3(cc);
        }
        u32*t=src;src=dst;dst=t;
    }
}

// L1: 5 u32 c1p,c2p,c3p,c4p,meta, merge by c2p, extract to L2 (4 u32)
static void cdq1(int N) {
    if (N<=1) return;
    u32*src=L1,*dst=T1;
    for(int w=1;w<N;w<<=1){
        for(int l=0;l<N;l+=2*w){ int mid=l+w;if(mid>N)mid=N; int r=l+2*w;if(r>N)r=N;
            if(mid>=r){ for(int t=l;t<r;t++){dst[5*t]=src[5*t];dst[5*t+1]=src[5*t+1];dst[5*t+2]=src[5*t+2];dst[5*t+3]=src[5*t+3];dst[5*t+4]=src[5*t+4];} continue; }
            int i=l,j=mid,k=l,cc=0;
            while(i<mid&&j<r){ u32 a0=src[5*i],a1=src[5*i+1],a2=src[5*i+2],a3=src[5*i+3],a4=src[5*i+4]; u32 b0=src[5*j],b1=src[5*j+1],b2=src[5*j+2],b3=src[5*j+3],b4=src[5*j+4]; int lf=(a1<=b1); u32 m=lf?a4:b4; dst[5*k]=lf?a0:b0;dst[5*k+1]=lf?a1:b1;dst[5*k+2]=lf?a2:b2;dst[5*k+3]=lf?a3:b3;dst[5*k+4]=m; L2[4*cc]=lf?a1:b1;L2[4*cc+1]=lf?a2:b2;L2[4*cc+2]=lf?a3:b3;L2[4*cc+3]=m; cc+=(lf^(m&1)); i+=lf;j+=1-lf;k++; }
            while(i<mid){ u32*e=src+5*i; dst[5*k]=e[0];dst[5*k+1]=e[1];dst[5*k+2]=e[2];dst[5*k+3]=e[3];dst[5*k+4]=e[4]; L2[4*cc]=e[1];L2[4*cc+1]=e[2];L2[4*cc+2]=e[3];L2[4*cc+3]=e[4]; cc+=!(e[4]&1); i++;k++; }
            while(j<r){ u32*e=src+5*j; dst[5*k]=e[0];dst[5*k+1]=e[1];dst[5*k+2]=e[2];dst[5*k+3]=e[3];dst[5*k+4]=e[4]; L2[4*cc]=e[1];L2[4*cc+1]=e[2];L2[4*cc+2]=e[3];L2[4*cc+3]=e[4]; cc+=(e[4]&1); j++;k++; }
            cdq2(cc);
        }
        u32*t=src;src=dst;dst=t;
    }
}

// L0: 6 u32 key,c1p,c2p,c3p,c4p,meta, merge by c1p, extract to L1 (5 u32)
static void cdq0(int N) {
    u32*src=L0,*dst=T0;
    for(int w=1;w<N;w<<=1){
        for(int l=0;l<N;l+=2*w){ int mid=l+w;if(mid>N)mid=N; int r=l+2*w;if(r>N)r=N;
            if(mid>=r){ for(int t=l;t<r;t++){dst[6*t]=src[6*t];dst[6*t+1]=src[6*t+1];dst[6*t+2]=src[6*t+2];dst[6*t+3]=src[6*t+3];dst[6*t+4]=src[6*t+4];dst[6*t+5]=src[6*t+5];} continue; }
            int i=l,j=mid,k=l,cc=0;
            while(i<mid&&j<r){ u32 a0=src[6*i],a1=src[6*i+1],a2=src[6*i+2],a3=src[6*i+3],a4=src[6*i+4],a5=src[6*i+5]; u32 b0=src[6*j],b1=src[6*j+1],b2=src[6*j+2],b3=src[6*j+3],b4=src[6*j+4],b5=src[6*j+5]; int lf=(a1<=b1); u32 m=lf?a5:b5; dst[6*k]=lf?a0:b0;dst[6*k+1]=lf?a1:b1;dst[6*k+2]=lf?a2:b2;dst[6*k+3]=lf?a3:b3;dst[6*k+4]=lf?a4:b4;dst[6*k+5]=m; L1[5*cc]=lf?a1:b1;L1[5*cc+1]=lf?a2:b2;L1[5*cc+2]=lf?a3:b3;L1[5*cc+3]=lf?a4:b4;L1[5*cc+4]=m; cc+=(lf^(m&1)); i+=lf;j+=1-lf;k++; }
            while(i<mid){ u32*e=src+6*i; dst[6*k]=e[0];dst[6*k+1]=e[1];dst[6*k+2]=e[2];dst[6*k+3]=e[3];dst[6*k+4]=e[4];dst[6*k+5]=e[5]; L1[5*cc]=e[1];L1[5*cc+1]=e[2];L1[5*cc+2]=e[3];L1[5*cc+3]=e[4];L1[5*cc+4]=e[5]; cc+=!(e[5]&1); i++;k++; }
            while(j<r){ u32*e=src+6*j; dst[6*k]=e[0];dst[6*k+1]=e[1];dst[6*k+2]=e[2];dst[6*k+3]=e[3];dst[6*k+4]=e[4];dst[6*k+5]=e[5]; L1[5*cc]=e[1];L1[5*cc+1]=e[2];L1[5*cc+2]=e[3];L1[5*cc+3]=e[4];L1[5*cc+4]=e[5]; cc+=(e[5]&1); j++;k++; }
            cdq1(cc);
        }
        u32*t=src;src=dst;dst=t;
    }
}

void count_5d(int n, const unsigned *x[5], unsigned *out) {
    memset(ans, 0, n*4);
    int m = 0;
    for (int i=0;i<n;i++) {
        u32* a = L0 + 6*m;
        a[0] = (x[0][i]+1u)*2u; a[1]=x[1][i]+1u; a[2]=x[2][i]+1u; a[3]=x[3][i]+1u; a[4]=x[4][i]+1u; a[5]=(u32)i*2u;
        m++;
        u32* q = L0 + 6*m;
        q[0] = x[0][i]*2u+1u; q[1]=x[1][i]; q[2]=x[2][i]; q[3]=x[3][i]; q[4]=x[4][i]; q[5]=(u32)i*2u+1u;
        m++;
    }
    rs0(m);
    cdq0(m);
    for (int i=0;i<n;i++) out[i] = ans[i];
}

评测结果