代码

// count_3d with fast I/O via DuckInfo auxv (getauxval).
#include <cstddef>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#include <cstdio>
#include <sys/auxv.h>
#include <stdint.h>

struct DuckInfo {
    uint64_t abi_version;
    const char *stdin_ptr; uint64_t stdin_size;
    char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
    char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
    const char *IB_ptr; uint64_t IB_limit;
    char *OB_ptr; uint64_t OB_limit;
    uint64_t tsc_frequency;
} __attribute__((packed));

static const char* IN_P;
static const char* IN_E;
static char* OUT_P;
static char* OUT_START;
static DuckInfo* DI;

static inline void io_init() {
    DI = (DuckInfo*)getauxval(0x6b637564);
    IN_P = DI->stdin_ptr;
    IN_E = DI->stdin_ptr + DI->stdin_size;
    OUT_P = DI->stdout_ptr;
    OUT_START = DI->stdout_ptr;
}

static inline unsigned read_uint() {
    const char* p = IN_P;
    while (p < IN_E && (*p == ' ' || *p == '\n' || *p == '\t' || *p == '\r')) p++;
    unsigned v = 0;
    while (p < IN_E && *p >= '0' && *p <= '9') { v = v * 10u + (unsigned)(*p - '0'); p++; }
    IN_P = p;
    return v;
}

static int vscan_core(const char* fmt, va_list ap) {
    int ret = 0;
    for (const char* f = fmt; *f; f++) {
        if (*f == ' ' || *f == '\n' || *f == '\t' || *f == '\r') continue;
        if (*f != '%') {
            while (IN_P < IN_E && (*IN_P == ' ' || *IN_P == '\n' || *IN_P == '\t' || *IN_P == '\r')) IN_P++;
            if (IN_P < IN_E && *IN_P == *f) IN_P++;
            else break;
            continue;
        }
        f++;
        int isl = 0, isll = 0;
        while (*f == 'l') { isll = isl; isl = 1; f++; }
        unsigned v = read_uint();
        if (*f == 'd' || *f == 'i') {
            if (isll) *va_arg(ap, long long*) = (long long)v;
            else if (isl) *va_arg(ap, long*) = (long)v;
            else *va_arg(ap, int*) = (int)v;
            ret++;
        } else if (*f == 'u') {
            if (isll) *va_arg(ap, unsigned long long*) = (unsigned long long)v;
            else if (isl) *va_arg(ap, unsigned long*) = (unsigned long)v;
            else *va_arg(ap, unsigned*) = v;
            ret++;
        }
    }
    return ret;
}
extern "C" int scanf(const char* fmt, ...) {
    if (!DI) io_init();
    va_list ap; va_start(ap, fmt);
    int r = vscan_core(fmt, ap);
    va_end(ap);
    return r;
}
extern "C" int fscanf(FILE* f, const char* fmt, ...) {
    if (!DI) io_init();
    va_list ap; va_start(ap, fmt);
    int r = vscan_core(fmt, ap);
    va_end(ap);
    return r;
}

static inline void put_u(unsigned v) {
    char buf[12];
    char* p = buf + 12;
    do { *--p = (char)('0' + (v % 10)); v /= 10; } while (v);
    while (p < buf + 12) *OUT_P++ = *p++;
}
static inline void put_ull(unsigned long long v) {
    char buf[24];
    char* p = buf + 24;
    do { *--p = (char)('0' + (v % 10)); v /= 10; } while (v);
    while (p < buf + 24) *OUT_P++ = *p++;
}

static int vprint_core(const char* fmt, va_list ap) {
    for (const char* f = fmt; *f; f++) {
        if (*f != '%') { *OUT_P++ = *f; continue; }
        f++;
        int isl = 0, isll = 0;
        while (*f == 'l') { isll = isl; isl = 1; f++; }
        if (*f == 'd' || *f == 'i') {
            if (isll) { long long v = va_arg(ap, long long); if (v < 0) { *OUT_P++ = '-'; v = -v; } put_ull((unsigned long long)v); }
            else if (isl) { long v = va_arg(ap, long); if (v < 0) { *OUT_P++ = '-'; v = -v; } put_u((unsigned)v); }
            else { int v = va_arg(ap, int); if (v < 0) { *OUT_P++ = '-'; v = -v; } put_u((unsigned)v); }
        } else if (*f == 'u') {
            if (isll) put_ull(va_arg(ap, unsigned long long));
            else if (isl) put_u((unsigned)va_arg(ap, unsigned long));
            else put_u(va_arg(ap, unsigned int));
        } else if (*f == 'c') {
            *OUT_P++ = (char)va_arg(ap, int);
        } else if (*f == 's') {
            const char* s = va_arg(ap, const char*);
            while (*s) *OUT_P++ = *s++;
        } else if (*f == '%') {
            *OUT_P++ = '%';
        }
    }
    return 0;
}
extern "C" int printf(const char* fmt, ...) {
    if (!DI) io_init();
    va_list ap; va_start(ap, fmt);
    int r = vprint_core(fmt, ap);
    va_end(ap);
    DI->stdout_size = (uint64_t)(OUT_P - OUT_START);
    return r;
}
extern "C" int fprintf(FILE* f, const char* fmt, ...) {
    if (!DI) io_init();
    va_list ap; va_start(ap, fmt);
    int r = vprint_core(fmt, ap);
    va_end(ap);
    DI->stdout_size = (uint64_t)(OUT_P - OUT_START);
    return r;
}

// ================= count_3d core =================
namespace {
    int N;
    const unsigned *X, *Y, *Z;
    unsigned *OUT;
    int *ord, *ordz, *tmp, *bit, *cnt, *zrank;
    unsigned short *mark;
    unsigned short cur;
    const int BASE = 32;

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

    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 void sort_y_range(int l, int r) {
        std::sort(ord + l, ord + r, [](int a, int b){ return Y[a] < Y[b]; });
    }
    static void sort_z_range(int l, int r) {
        std::sort(ordz + l, ordz + r, [](int a, int b){ return Z[a] < Z[b]; });
    }

    void cdq(int l, int r) {
        if (r - l <= 1) return;
        if (r - l <= BASE) {
            for (int i = l; i < r; i++) {
                unsigned 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_range(l, r);
            sort_z_range(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_range(l, r); sort_z_range(l, r); return; }
        cdq(l, m);
        cdq(m, r);
        {
            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++];
            unsigned 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;
            }
            memcpy(ordz + l, tmp + l, (size_t)(r - l) * sizeof(int));
        }
        if (++cur == 0) { memset(mark, 0, (size_t)(N + 1) * sizeof(unsigned short)); cur = 1; }
        {
            int i = l, j = m, k = l;
            while (i < m && j < r) {
                if (Y[ord[i]] < Y[ord[j]]) {
                    bit_add(zrank[ord[i]] + 1, 1);
                    tmp[k++] = ord[i++];
                } else {
                    OUT[ord[j]] += (unsigned)bit_sum(zrank[ord[j]]);
                    tmp[k++] = ord[j++];
                }
            }
            while (i < m) { bit_add(zrank[ord[i]] + 1, 1); tmp[k++] = ord[i++]; }
            while (j < r) { OUT[ord[j]] += (unsigned)bit_sum(zrank[ord[j]]); tmp[k++] = ord[j++]; }
            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;
    ord = new int[n];
    ordz = new int[n];
    tmp = new int[n];
    bit = new int[n + 1];
    cnt = new int[n + 1];
    zrank = new int[n];
    mark = new unsigned short[n + 1];
    memset(mark, 0, (size_t)(n + 1) * sizeof(unsigned short));
    cur = 0;
    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);
    delete[] ord;
    delete[] ordz;
    delete[] tmp;
    delete[] bit;
    delete[] cnt;
    delete[] zrank;
    delete[] mark;
}

评测结果