代码

// count_3d: 3D strict dominance counting via CDQ.
// Sort by x (counting sort), split each CDQ node at an x-group boundary so that
// cross pairs always have x_left < x_right (strict). Merge by y (strict), BIT on z (strict).
#include <cstddef>
#include <cstring>
#include <algorithm>

namespace {
    int N;
    const unsigned *X, *Y, *Z;
    unsigned *OUT;
    int *ord, *tmp, *bit, *cnt;

    static inline void bit_add(int i, int v) {
        for (; i <= N; i += i & -i) bit[i] += v;
    }
    static inline int bit_sum(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }

    // counting sort ord[0..n) by X (X in [0,n))
    static void sort_by_x(int n) {
        for (int i = 0; i < n; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[X[i]]++;
        int acc = 0;
        for (int v = 0; v < n; v++) { int c = cnt[v]; cnt[v] = acc; acc += c; }
        for (int i = 0; i < n; i++) ord[cnt[X[i]]++] = i;
    }

    static void sort_y_range(int l, int r) {
        std::sort(ord + l, ord + r, [](int a, int b){ return Y[a] < Y[b]; });
    }

    // cdq on ord[l..r) which is x-sorted on entry; on exit it is y-sorted.
    void cdq(int l, int r) {
        if (r - l <= 1) return;
        int m = (l + r) >> 1;
        // find the x-group containing position m: [gs, ge] inclusive
        int gs = m;
        while (gs > l && X[ord[gs - 1]] == X[ord[gs]]) gs--;
        int ge = m;
        while (ge + 1 < r && X[ord[ge + 1]] == X[ord[ge]]) ge++;
        if (gs > l) {
            m = gs;
        } else if (ge + 1 < r) {
            m = ge + 1;
        } else {
            // entire segment is one x-group: no cross contributions (strict x fails)
            sort_y_range(l, r);
            return;
        }
        cdq(l, m);
        cdq(m, r);
        // merge [l,m) and [m,r) (both y-sorted) with BIT cross-counting (strict y, strict z)
        int i = l, j = m, k = l;
        while (i < m && j < r) {
            if (Y[ord[i]] < Y[ord[j]]) {
                bit_add((int)Z[ord[i]] + 1, 1);
                tmp[k++] = ord[i++];
            } else {
                OUT[ord[j]] += (unsigned)bit_sum((int)Z[ord[j]]);
                tmp[k++] = ord[j++];
            }
        }
        while (i < m) { bit_add((int)Z[ord[i]] + 1, 1); tmp[k++] = ord[i++]; }
        while (j < r) { OUT[ord[j]] += (unsigned)bit_sum((int)Z[ord[j]]); tmp[k++] = ord[j++]; }
        for (int t = l; t < m; t++) bit_add((int)Z[ord[t]] + 1, -1);
        memcpy(ord + l, tmp + l, (size_t)(r - l) * sizeof(int));
    }
}

void count_3d(int n, const unsigned *x, const unsigned *y, const unsigned *z, unsigned *out) {
    N = n; X = x; Y = y; Z = z; OUT = out;
    ord = new int[n];
    tmp = new int[n];
    bit = new int[n + 1];
    cnt = new int[n + 1];
    for (int i = 0; i < n; i++) ord[i] = i;
    sort_by_x(n);
    memset(bit, 0, (size_t)(n + 1) * sizeof(int));
    cdq(0, n);
    delete[] ord;
    delete[] tmp;
    delete[] bit;
    delete[] cnt;
}

评测结果