代码

// v4: +1-offset unsigned coords; packed u64; vectorized counter (branchless prefix-sum)
#pragma GCC target("avx2")
#include <cstring>
#include <immintrin.h>
typedef unsigned u32; typedef int i32; typedef unsigned long long u64;
static u32 ans[300000];
static u32 L0[5*600002]; static u32 T0[5*600002];
static u64 L1[600002]; static u64 T1[600002];
static u64 L2[600002]; static u64 T2[600002];
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[5*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+5*i; u32 p=cnt[e[0]&0xFFFF]++; u32*d=T0+5*p; d[0]=e[0];d[1]=e[1];d[2]=e[2];d[3]=e[3];d[4]=e[4]; }
    memset(cnt,0,sizeof(cnt)); for(int i=0;i<m;i++) cnt[T0[5*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+5*i; u32 p=cnt[e[0]>>16]++; u32*d=L0+5*p; d[0]=e[0];d[1]=e[1];d[2]=e[2];d[3]=e[3];d[4]=e[4]; }
}

// level 2: merge sort L2[0..N) by c3p (low 19 bits), fused-free counter via L3-less:
// L2 event: c3p (0..18) | meta<<19. We process counter AFTER merge per node (v6 style with L3? no)
// Use separate L3 for counter (v6 style): extract meta to L3.
static u32 L3[600002];
static void cdq3(int l,int r){
    u32 c=0;
    const __m256i z=_mm256_setzero_si256();
    const __m256i one=_mm256_set1_epi32(1);
    const __m256i idx1=_mm256_setr_epi32(7,0,1,2,3,4,5,6);
    const __m256i idx2=_mm256_setr_epi32(6,7,0,1,2,3,4,5);
    const __m256i idx4=_mm256_setr_epi32(4,5,6,7,0,1,2,3);
    while(l+8<=r){
        __m256i v=_mm256_loadu_si256((const __m256i*)(L3+l));
        __m256i isq=_mm256_and_si256(v,one);          // 1=query, 0=point
        __m256i ispt=_mm256_xor_si256(isq,one);       // 1=point, 0=query
        __m256i s=ispt;
        __m256i t=_mm256_permutevar8x32_epi32(s,idx1); t=_mm256_blend_epi32(t,z,0x01); s=_mm256_add_epi32(s,t);
        t=_mm256_permutevar8x32_epi32(s,idx2); t=_mm256_blend_epi32(t,z,0x03); s=_mm256_add_epi32(s,t);
        t=_mm256_permutevar8x32_epi32(s,idx4); t=_mm256_blend_epi32(t,z,0x0F); s=_mm256_add_epi32(s,t);
        __m256i ex=_mm256_sub_epi32(s,ispt);          // exclusive prefix of points
        __m256i addv=_mm256_add_epi32(ex,_mm256_set1_epi32(c));
        c += _mm256_extract_epi32(s,7);               // total points in block
        __m256i qm=_mm256_cmpgt_epi32(isq,z);         // -1 for query
        int mask=_mm256_movemask_ps(_mm256_castsi256_ps(qm));
        if(mask){
            u32 m8[8],a8[8];
            _mm256_storeu_si256((__m256i*)m8,v);
            _mm256_storeu_si256((__m256i*)a8,addv);
            while(mask){ int i=__builtin_ctz(mask); ans[m8[i]>>1]+=a8[i]; mask&=mask-1; }
        }
        l+=8;
    }
    for(;l<r;l++){ u32 m=L3[l]; if(m&1) ans[m>>1]+=c; else c++; }
}

static void cdq2(int N) {
    if (N <= 1) return;
    u64* src = L2, *dst = T2;
    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 & M19) <= (aj & M19));
                u64 s = lf ? ai : aj; u32 m=(u32)(s>>19);
                dst[k]=s; L3[cc]=m; cc += (lf ^ (m&1));
                i += lf; j += 1-lf; k++;
            }
            while (i<mid) { u64 s=src[i]; u32 m=(u32)(s>>19); dst[k]=s; L3[cc]=m; cc += !(m&1); i++; k++; }
            while (j<r)  { u64 s=src[j]; u32 m=(u32)(s>>19); dst[k]=s; L3[cc]=m; cc += (m&1); j++; k++; }
            cdq3(cc0, cc);
        }
        u64* t = src; src = dst; dst = t;
    }
}

// level 1: merge L1[0..N) by c2p (low 19), extract {c3p,meta} to L2 (u64: c3p | meta<<19)
static void cdq1(int N) {
    if (N <= 1) return;
    u64* 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[t]=src[t]; continue; }
            int i=l,j=mid,k=l,cc=0;
            while (i<mid && j<r) {
                u64 ai=src[i], aj=src[j];
                int lf = ((ai & M19) <= (aj & M19));
                u64 s = lf ? ai : aj;
                u32 m = (u32)(s >> 38);
                dst[k]=s;
                L2[cc] = ((s >> 19) & M19) | ((u64)m << 19);
                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; L2[cc]=((s>>19)&M19)|((u64)m<<19); cc += !(m&1); i++;k++; }
            while (j<r)  { u64 s=src[j]; u32 m=(u32)(s>>38); dst[k]=s; L2[cc]=((s>>19)&M19)|((u64)m<<19); cc += (m&1); j++;k++; }
            cdq2(cc);
        }
        u64* t = src; src = dst; dst = t;
    }
}

// level 0: merge L0[0..N) (5 u32: key,c1p,c2p,c3p,meta) by c1p (word1), extract to L1 (u64: c2p|c3p<<19|meta<<38)
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[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;
                u32 c2=lf?a2:b2, c3=lf?a3:b3;
                L1[cc] = (u64)c2 | ((u64)c3 << 19) | ((u64)m << 38);
                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]; L1[cc]=(u64)e[2]|((u64)e[3]<<19)|((u64)e[4]<<38); 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]; L1[cc]=(u64)e[2]|((u64)e[3]<<19)|((u64)e[4]<<38); cc += (e[4]&1); j++;k++; }
            cdq1(cc);
        }
        u32* t = src; src = dst; dst = t;
    }
}

void count_4d(int n, const unsigned *x[4], unsigned *out) {
    memset(ans, 0, n*4);
    int m = 0;
    for (int i=0;i<n;i++) {
        u32* a = L0 + 5*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]=(u32)i*2u;
        m++;
        u32* q = L0 + 5*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]=(u32)i*2u+1u;
        m++;
    }
    rs0(m);
    cdq0(m);
    for (int i=0;i<n;i++) out[i] = ans[i];
}

评测结果