代码

// 4D dominance (strict) — events CDQ, no Fenwick (last level sorted => running counter).
#include <cstring>
#include <algorithm>

typedef unsigned u32;

struct Ev {
    int c[4];
    u32 meta;   // (id << 1) | typ
};

#define TYP(e) ((e).meta & 1u)
#define ID(e) ((int)((e).meta >> 1))

static Ev buf[4][600002];
static Ev tmp[600002];
static u32 ans[300000];

void cdq(int d, int l, int r) {
    if (r - l <= 1) return;
    if (d == 3) {
        Ev *b = buf[3];
        int cnt = 0;
        for (int i = l; i < r; i++) {
            if (TYP(b[i]) == 0) cnt++;
            else ans[ID(b[i])] += (u32)cnt;
        }
        return;
    }
    int mid = (l + r) >> 1;
    cdq(d, l, mid);
    cdq(d, mid, r);
    Ev *b = buf[d];
    Ev *bn = buf[d + 1];
    int i = l, j = mid, k = l, cc = 0;
    while (i < mid && j < r) {
        if (b[i].c[d + 1] <= b[j].c[d + 1]) {
            Ev e = b[i++];
            tmp[k++] = e;
            if (TYP(e) == 0) bn[cc++] = e;
        } else {
            Ev e = b[j++];
            tmp[k++] = e;
            if (TYP(e) == 1) bn[cc++] = e;
        }
    }
    while (i < mid) { Ev e = b[i++]; tmp[k++] = e; if (TYP(e) == 0) bn[cc++] = e; }
    while (j < r)  { Ev e = b[j++]; tmp[k++] = e; if (TYP(e) == 1) bn[cc++] = e; }
    memcpy(b + l, tmp + l, (size_t)(r - l) * sizeof(Ev));
    cdq(d + 1, 0, cc);
}

void count_4d(int n, const unsigned *x[4], unsigned *out) {
    memset(ans, 0, sizeof(u32) * n);
    int m = 0;
    for (int i = 0; i < n; i++) {
        Ev &a = buf[0][m++];
        a.c[0] = (int)x[0][i]; a.c[1] = (int)x[1][i];
        a.c[2] = (int)x[2][i]; a.c[3] = (int)x[3][i];
        a.meta = ((u32)i << 1) | 0u;
        Ev &q = buf[0][m++];
        q.c[0] = (int)x[0][i] - 1; q.c[1] = (int)x[1][i] - 1;
        q.c[2] = (int)x[2][i] - 1; q.c[3] = (int)x[3][i] - 1;
        q.meta = ((u32)i << 1) | 1u;
    }
    std::sort(buf[0], buf[0] + m, [](const Ev &a, const Ev &b) {
        if (a.c[0] != b.c[0]) return a.c[0] < b.c[0];
        return TYP(a) < TYP(b);
    });
    cdq(0, 0, m);
    for (int i = 0; i < n; i++) out[i] = ans[i];
}

评测结果