代码

// This code is AI-generated. (AI 生成的代码)
// 3D strict dominance via CDQ on x.  Each CDQ node compresses its own z values
// and uses a plain Fenwick of size = number of distinct z in the node, cleared
// with one memset; small nodes are solved by brute force.  y and z are kept
// mergesorted so the parent only has to merge.
#include <cstring>
typedef unsigned u32;
typedef unsigned long U;

#ifndef CAPACITY
#define CAPACITY 1000005
#endif
enum { MAXN = CAPACITY, BASE = 16 };

static int N;
static const u32 *X, *Y, *Z;
static u32 *OUT;
static int ord[MAXN], ordz[MAXN], tmp[MAXN], bit[MAXN + 1], zrank[MAXN], cnt[MAXN + 1];

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 inline void sort_y(int l, int r) {
    for (int i = l + 1; i < r; i++) {
        int v = ord[i]; u32 vy = Y[v]; int j = i - 1;
        while (j >= l && Y[ord[j]] > vy) { ord[j + 1] = ord[j]; --j; }
        ord[j + 1] = v;
    }
}
static inline void sort_z(int l, int r) {
    for (int i = l + 1; i < r; i++) {
        int v = ordz[i]; u32 vz = Z[v]; int j = i - 1;
        while (j >= l && Z[ordz[j]] > vz) { ordz[j + 1] = ordz[j]; --j; }
        ordz[j + 1] = v;
    }
}

static void cdq(int l, int r) {
    if (r - l <= 1) return;
    if (r - l <= BASE) {
        for (int i = l; i < r; i++) {
            u32 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(l, r);
        sort_z(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(l, r); sort_z(l, r); return; }

    cdq(l, m);
    cdq(m, r);

    // merge z, assign compressed ranks
    int D;
    {
        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++];
        u32 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;
        }
        D = rk + 1;
        memcpy(ordz + l, tmp + l, (size_t)(r - l) * sizeof(int));
    }
    memset(bit, 0, (size_t)(D + 1) * sizeof(int));
    {
        int i = l, j = m, k = l;
        while (i < m && j < r) {
            if (Y[ord[i]] < Y[ord[j]]) {
                int v = ord[i++];
                for (int x = zrank[v] + 1; x <= D; x += x & -x) ++bit[x];
                tmp[k++] = v;
            } else {
                int v = ord[j++], s = 0;
                for (int x = zrank[v]; x > 0; x -= x & -x) s += bit[x];
                OUT[v] += (u32)s;
                tmp[k++] = v;
            }
        }
        while (i < m) {
            int v = ord[i++];
            for (int x = zrank[v] + 1; x <= D; x += x & -x) ++bit[x];
            tmp[k++] = v;
        }
        while (j < r) {
            int v = ord[j++], s = 0;
            for (int x = zrank[v]; x > 0; x -= x & -x) s += bit[x];
            OUT[v] += (u32)s;
            tmp[k++] = v;
        }
        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;
    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);
}

#ifndef LOCAL
static char **initial_argv;
static U initial_argc;

U getauxval(U key) {
    char **p = initial_argv + initial_argc + 1;
    while (*p) ++p;
    U *aux = (U *)(p + 1);
    while (aux[0]) {
        if (aux[0] == key) return aux[1];
        aux += 2;
    }
    return 0;
}

__attribute__((noreturn))
void __libc_start_main(int (*entry)(int, char **, char **), int argc, char **argv) {
    initial_argc = (U)argc;
    initial_argv = argv;
    entry(argc, argv, (char **)0);
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall"
                     ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}
#endif

评测结果