代码

// 2D dominance: radix-sort by x -> gather y -> 2-level Fenwick (B=256).
#include <cstring>
typedef unsigned u32; typedef unsigned long long u64;

static u64 keys[10000000];
static u64 temp[10000000];
static int cnt16[65536];
static unsigned ysort[10000000];
static u32 topFen[40000];
static u32 botFen[10001000];

static inline void radix3(u64 *a, u64 *b, int n) {
    for (int shift = 0; shift < 48; shift += 16) {
        memset(cnt16, 0, sizeof(cnt16));
        for (int i = 0; i < n; i++) cnt16[(a[i] >> shift) & 0xFFFF]++;
        for (int i = 1; i < 65536; i++) cnt16[i] += cnt16[i-1];
        for (int i = n-1; i >= 0; i--) b[--cnt16[(a[i] >> shift) & 0xFFFF]] = a[i];
        u64 *t = a; a = b; b = t;
    }
    if (a != keys) { for (int i = 0; i < n; i++) keys[i] = a[i]; }
}

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    for (int i = 0; i < n; i++) keys[i] = ((u64)x[i] << 24) | (u64)(unsigned)i;
    radix3(keys, temp, n);
    // gather y into x-order
    for (int k = 0; k < n; k++) ysort[k] = y[(int)(keys[k] & 0xFFFFFFu)];

    int NB = n >> 8;
    int k = 0;
    while (k < n) {
        u32 cur_x = (u32)(keys[k] >> 24);
        int kk = k + 1;
        while (kk < n && (u32)(keys[kk] >> 24) == cur_x) kk++;
        for (int t = k; t < kk; ++t) {
            u32 yy = ysort[t];
            u32 b = yy >> 8, c = yy & 255;
            u32 s = 0;
            for (u32 j = b; j; j &= j - 1) s += topFen[j];
            u32 base = b << 8;
            for (u32 j = c; j; j &= j - 1) s += botFen[base + j];
            out[(int)(keys[t] & 0xFFFFFFu)] = s;
        }
        for (int t = k; t < kk; ++t) {
            u32 yy = ysort[t];
            u32 b = yy >> 8, c = yy & 255;
            u32 base = b << 8;
            for (u32 j = c + 1; j <= 256; j += j & -j) botFen[base + j]++;
            for (u32 j = b + 1; j <= (u32)NB; j += j & -j) topFen[j]++;
        }
        k = kk;
    }
}

评测结果