代码

// Variant: per-node z-compression (merge-based) + timestamp Fenwick (16-bit mark) + base case.
// No rollback: timestamp reset; small per-node BIT keeps mark hot in cache.
#include <cstddef>
#include <cstring>
#include <algorithm>

namespace {
    int N;
    const unsigned *X, *Y, *Z;
    unsigned *OUT;
    int *ord, *ordz, *tmp, *bit, *cnt, *zrank;
    unsigned short *mark;
    unsigned short cur;
    const int BASE = 48;

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

    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]; });
    }
    static void sort_z_range(int l, int r) {
        std::sort(ordz + l, ordz + r, [](int a, int b){ return Z[a] < Z[b]; });
    }

    void cdq(int l, int r) {
        if (r - l <= 1) return;
        if (r - l <= BASE) {
            for (int i = l; i < r; i++) {
                unsigned xi = X[ord[i]], yi = Y[ord[i]], zi = Z[ord[i]];
                for (int j = i + 1; j < r; j++) {
                    if (xi < X[ord[j]] && yi < Y[ord[j]] && zi < Z[ord[j]]) OUT[ord[j]]++;
                }
            }
            sort_y_range(l, r);
            sort_z_range(l, r);
            return;
        }
        int m = (l + r) >> 1;
        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 { sort_y_range(l, r); sort_z_range(l, r); return; }
        cdq(l, m);
        cdq(m, r);
        // z-merge ordz[l..m) and ordz[m..r) into tmp, assign local ranks
        {
            int i = l, j = m, k = l;
            while (i < m && j < r) {
                if (Z[ordz[i]] <= Z[ordz[j]]) tmp[k++] = ordz[i++];
                else tmp[k++] = ordz[j++];
            }
            while (i < m) tmp[k++] = ordz[i++];
            while (j < r) tmp[k++] = ordz[j++];
            unsigned prev = Z[tmp[l]];
            int rk = 0;
            zrank[tmp[l]] = 0;
            for (int t = l + 1; t < r; t++) {
                if (Z[tmp[t]] != prev) { rk++; prev = Z[tmp[t]]; }
                zrank[tmp[t]] = rk;
            }
            memcpy(ordz + l, tmp + l, (size_t)(r - l) * sizeof(int));
        }
        // y-merge with timestamp BIT over local ranks
        if (++cur == 0) { memset(mark, 0, (size_t)(N + 1) * sizeof(unsigned short)); cur = 1; }
        {
            int i = l, j = m, k = l;
            while (i < m && j < r) {
                if (Y[ord[i]] < Y[ord[j]]) {
                    bit_add(zrank[ord[i]] + 1, 1);
                    tmp[k++] = ord[i++];
                } else {
                    OUT[ord[j]] += (unsigned)bit_sum(zrank[ord[j]]);
                    tmp[k++] = ord[j++];
                }
            }
            while (i < m) { bit_add(zrank[ord[i]] + 1, 1); tmp[k++] = ord[i++]; }
            while (j < r) { OUT[ord[j]] += (unsigned)bit_sum(zrank[ord[j]]); tmp[k++] = ord[j++]; }
            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];
    ordz = new int[n];
    tmp = new int[n];
    bit = new int[n + 1];
    cnt = new int[n + 1];
    zrank = new int[n];
    mark = new unsigned short[n + 1];
    memset(mark, 0, (size_t)(n + 1) * sizeof(unsigned short));
    cur = 0;
    for (int i = 0; i < n; i++) ord[i] = i;
    sort_by_x(n);
    for (int i = 0; i < n; i++) ordz[i] = ord[i];
    cdq(0, n);
    delete[] ord;
    delete[] ordz;
    delete[] tmp;
    delete[] bit;
    delete[] cnt;
    delete[] zrank;
    delete[] mark;
}

评测结果