代码

// 5D dominance counting (strict) via nested CDQ.
#include <cstring>
#include <algorithm>

typedef unsigned u32;

struct Ev {
    int c[5];
    int typ;   // 0 = add, 1 = query
    int id;
};

static Ev buf[5][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 == 4) {
        Ev *b = buf[4];
        for (int i = l; i < r; i++) {
            if (b[i].typ == 0) bit_add(b[i].c[4], 1);
            else ans[b[i].id] += (u32)bit_sum(b[i].c[4]);
        }
        for (int i = l; i < r; i++) if (b[i].typ == 0) bit_add(b[i].c[4], -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) {
        if (b[i].c[d + 1] <= b[j].c[d + 1]) {
            Ev e = b[i++];
            if (e.typ == 0) bn[cc++] = e;
            tmp[k++] = e;
        } else {
            Ev e = b[j++];
            if (e.typ == 1) bn[cc++] = e;
            tmp[k++] = e;
        }
    }
    while (i < mid) { Ev e = b[i++]; if (e.typ == 0) bn[cc++] = e; tmp[k++] = e; }
    while (j < r)  { Ev e = b[j++]; if (e.typ == 1) bn[cc++] = e; tmp[k++] = e; }
    memcpy(b + l, tmp + l, (size_t)(r - l) * sizeof(Ev));
    cdq(d + 1, 0, cc);
}

void count_5d(int n, const unsigned *x[5], 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.c[4] = (int)x[4][i];
        a.typ = 0; a.id = i;
        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.c[4] = (int)x[4][i] - 1;
        q.typ = 1; q.id = 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];
        return a.typ < b.typ;
    });
    cdq(0, 0, m);
    for (int i = 0; i < n; i++) out[i] = ans[i];
}

评测结果