代码

/* 3D dominance counting: out[i] = #{ j : x[j]<x[i] && y[j]<y[i] && z[j]<z[i] }.
 * CDQ over the x-sorted (time) axis with x-group boundary splits; merge by y;
 * timestamped Fenwick tree over z (no undo pass).  Brute force base case. */
typedef unsigned u32;

static int N;
static u32 *AY, *AZ;     /* permuted by y (during the algorithm), initially time order */
static int *AO;          /* original index of each permuted slot */
static int *TMPO;
static u32 *TMPY, *TMPZ;
static u32 *BIT;
static u32 *BST;         /* BIT stamp */
static u32 CURSTAMP;
static u32 *ANS;         /* indexed by original index */
static int *GSTART, *GNEXT;

static inline void bit_add(int i) {
    u32 st = CURSTAMP;
    for (; i <= N; i += i & (-i)) {
        if (BST[i] != st) { BST[i] = st; BIT[i] = 1; }
        else BIT[i]++;
    }
}
static inline u32 bit_sum(int i) {
    u32 s = 0, st = CURSTAMP;
    for (; i > 0; i -= i & (-i)) if (BST[i] == st) s += BIT[i];
    return s;
}

static inline void sort_y(int l, int r) {
    for (int i = l + 1; i < r; i++) {
        u32 vy = AY[i], vz = AZ[i];
        int vo = AO[i];
        int j = i - 1;
        while (j >= l && AY[j] > vy) {
            AY[j + 1] = AY[j]; AZ[j + 1] = AZ[j]; AO[j + 1] = AO[j];
            j--;
        }
        AY[j + 1] = vy; AZ[j + 1] = vz; AO[j + 1] = vo;
    }
}

#define BASE 64

static void cdq(int l, int r) {
    int len = r - l;
    if (len <= 1) return;
    if (len <= BASE) {
        for (int a = l; a < r; a++) {
            u32 ya = AY[a], za = AZ[a];
            for (int b = a + 1; b < r; b++)
                if (ya < AY[b] && za < AZ[b]) ANS[AO[b]]++;
        }
        sort_y(l, r);
        return;
    }
    if (GSTART[l] == GSTART[r - 1]) { sort_y(l, r); return; }
    int mid = (l + r) >> 1;
    int gs = GSTART[mid];
    mid = (gs > l) ? gs : GNEXT[gs];
    if (mid <= l || mid >= r) { sort_y(l, r); return; }

    cdq(l, mid);
    cdq(mid, r);

    CURSTAMP++;
    int a = l;
    for (int j = mid; j < r; j++) {
        u32 yj = AY[j];
        while (a < mid && AY[a] < yj) { bit_add((int)AZ[a] + 1); a++; }
        ANS[AO[j]] += bit_sum((int)AZ[j]);
    }
    /* merge [l,mid) and [mid,r) by y */
    int i = l, k = l, m = mid;
    while (i < mid && m < r) {
        if (AY[i] <= AY[m]) { TMPY[k] = AY[i]; TMPZ[k] = AZ[i]; TMPO[k] = AO[i]; i++; }
        else { TMPY[k] = AY[m]; TMPZ[k] = AZ[m]; TMPO[k] = AO[m]; m++; }
        k++;
    }
    while (i < mid) { TMPY[k] = AY[i]; TMPZ[k] = AZ[i]; TMPO[k] = AO[i]; i++; k++; }
    while (m < r) { TMPY[k] = AY[m]; TMPZ[k] = AZ[m]; TMPO[k] = AO[m]; m++; k++; }
    for (k = l; k < r; k++) { AY[k] = TMPY[k]; AZ[k] = TMPZ[k]; AO[k] = TMPO[k]; }
}

void count_3d(int n, const unsigned *x, const unsigned *y, const unsigned *z, unsigned *out) {
    N = n;
    if (n <= 0) return;
    static u32 *ay0, *az0, *bit0, *bst0, *ans0, *cnt0;
    static int *ao0, *tmpo0, *gs0; static u32 *tmpy0, *tmpz0;
    if (!ay0) {
        ay0 = new u32[n]; az0 = new u32[n]; bit0 = new u32[n + 1]; bst0 = new u32[n + 1];
        ans0 = new u32[n]; cnt0 = new u32[n + 1];
        ao0 = new int[n]; tmpo0 = new int[n]; tmpy0 = new u32[n]; tmpz0 = new u32[n];
        gs0 = new int[2 * n + 2];
    }
    AY = ay0; AZ = az0; BIT = bit0; BST = bst0; ANS = ans0;
    AO = ao0; TMPY = tmpy0; TMPZ = tmpz0; TMPO = tmpo0;
    GSTART = gs0; GNEXT = gs0 + n + 1;
    /* stable counting sort by x -> time order in (AY,AZ,AO) */
    {
        u32 *cnt = cnt0;
        for (int i = 0; i <= n; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[x[i]]++;
        u32 s = 0;
        for (int v = 0; v <= n; v++) { u32 c = cnt[v]; cnt[v] = s; s += c; }
        for (int i = 0; i < n; i++) {
            int p = (int)cnt[x[i]]++;
            AY[p] = y[i]; AZ[p] = z[i]; AO[p] = i;
        }
    }
    for (int i = 0; i <= n; i++) { BIT[i] = 0; BST[i] = 0; }
    for (int i = 0; i < n; i++) ANS[i] = 0;
    CURSTAMP = 0;
    {
        int t = 0;
        while (t < n) {
            u32 xv = (u32)x[AO[t]];
            int e = t;
            while (e < n && (u32)x[AO[e]] == xv) e++;
            for (int k = t; k < e; k++) GSTART[k] = t;
            GNEXT[t] = e;
            t = e;
        }
        GNEXT[n] = n;
    }
    cdq(0, n);
    for (int t = 0; t < n; t++) out[AO[t]] = ANS[AO[t]];
}

评测结果