代码

// 4D dominance (strict) — events CDQ, branchless merge.
#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 int bit[300002];
static u32 ans[300000];
static int N;

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

void cdq(int d, int l, int r) {
    if (r - l <= 1) return;
    if (d == 3) {
        Ev *b = buf[3];
        for (int i = l; i < r; i++) {
            if (TYP(b[i]) == 0) bit_add(b[i].c[3], 1);
            else ans[ID(b[i])] += (u32)bit_sum(b[i].c[3]);
        }
        for (int i = l; i < r; i++) if (TYP(b[i]) == 0) bit_add(b[i].c[3], -1);
        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) {
        int take_left = (b[i].c[d + 1] <= b[j].c[d + 1]) ? 1 : 0;
        Ev e = take_left ? b[i] : b[j];
        int is_add = (TYP(e) == 0) ? 1 : 0;
        int extract = (take_left == is_add) ? 1 : 0;
        bn[cc] = e;
        cc += extract;
        tmp[k++] = e;
        i += take_left;
        j += 1 - take_left;
    }
    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) {
    N = n;
    memset(bit, 0, sizeof(int) * (n + 2));
    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];
}

评测结果