代码

// 4D dominance (strict) — DIRECT CDQ (1x events), split-at-boundary + strict running counter.
#include <cstring>
#include <algorithm>

typedef unsigned u32;

struct Ev {
    int c[4];
    int g;   // g>=0 => add (point g); g<0 => query (point -g-1)
};

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

// find a boundary index b in (l,r) with c[d][b-1] != c[d][b], near mid. -1 if all equal.
static inline int boundary(int d, int l, int r, int mid) {
    Ev *b = buf[d];
    int v = b[mid].c[d];
    int lo = l, hi = mid;
    while (lo < hi) { int m = (lo + hi) >> 1; if (b[m].c[d] < v) lo = m + 1; else hi = m; }
    int run_start = lo;
    lo = run_start; hi = r;
    while (lo < hi) { int m = (lo + hi) >> 1; if (b[m].c[d] <= v) lo = m + 1; else hi = m; }
    int run_end = lo;
    if (run_start > l && run_end < r) return (mid - run_start <= run_end - mid) ? run_start : run_end;
    if (run_start > l) return run_start;
    if (run_end < r) return run_end;
    return -1;
}

void cdq(int d, int l, int r) {
    if (r - l <= 1) return;
    if (d == 3) {
        Ev *b = buf[3];
        int cnt_lt = 0, cnt_eq = 0;
        int prev = -2147483647 - 1;
        for (int i = l; i < r; i++) {
            int v = b[i].c[3];
            if (v != prev) { cnt_lt += cnt_eq; cnt_eq = 0; prev = v; }
            if (b[i].g >= 0) cnt_eq++;
            else ans[-b[i].g - 1] += (u32)cnt_lt;
        }
        return;
    }
    int mid0 = (l + r) >> 1;
    int bnd = boundary(d, l, r, mid0);
    bool has_bnd = (bnd >= 0);
    int mid = has_bnd ? bnd : mid0;
    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;
    if (has_bnd) {
        while (i < mid && j < r) {
            if (b[i].c[d + 1] <= b[j].c[d + 1]) {
                Ev e = b[i++];
                tmp[k++] = e;
                if (e.g >= 0) bn[cc++] = e;
            } else {
                Ev e = b[j++];
                tmp[k++] = e;
                if (d == 0) { e.g = -(e.g + 1); bn[cc++] = e; }
                else if (e.g < 0) bn[cc++] = e;
            }
        }
        while (i < mid) { Ev e = b[i++]; tmp[k++] = e; if (e.g >= 0) bn[cc++] = e; }
        while (j < r)  {
            Ev e = b[j++];
            tmp[k++] = e;
            if (d == 0) { e.g = -(e.g + 1); bn[cc++] = e; }
            else if (e.g < 0) bn[cc++] = e;
        }
    } else {
        while (i < mid && j < r) {
            if (b[i].c[d + 1] <= b[j].c[d + 1]) tmp[k++] = b[i++];
            else tmp[k++] = b[j++];
        }
        while (i < mid) tmp[k++] = b[i++];
        while (j < r)  tmp[k++] = b[j++];
    }
    memcpy(b + l, tmp + l, (size_t)(r - l) * sizeof(Ev));
    if (has_bnd) 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.g = i;
    }
    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];
        if (a.c[1] != b.c[1]) return a.c[1] < b.c[1];
        if (a.c[2] != b.c[2]) return a.c[2] < b.c[2];
        return a.c[3] < b.c[3];
    });
    cdq(0, 0, m);
    for (int i = 0; i < n; i++) out[i] = ans[i];
}

评测结果