代码

// 2D dominance: radix-sort (x,y) pairs permuting original index -> 2-level Fenwick.
#include <cstring>
typedef unsigned u32; typedef unsigned long long u64;

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

// 4-pass LSD radix sort (16-bit) on 64-bit keys, permuting idx alongside.
// Always leaves the sorted result in keys[]/idx[].
static void radix4(int n) {
    u64 *a = keys, *b = temp;
    u32 *ia = idx, *ib = temp_idx;
    for (int shift = 0; shift < 64; 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--) {
            int pos = --cnt16[(a[i] >> shift) & 0xFFFF];
            b[pos] = a[i]; ib[pos] = ia[i];
        }
        u64 *tk = a; a = b; b = tk;
        u32 *ti = ia; ia = ib; ib = ti;
    }
    if (a != keys) { memcpy(keys, a, (size_t)n*8); memcpy(idx, ia, (size_t)n*4); }
}

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] << 32) | y[i]; idx[i] = (u32)i; }
    radix4(n);

    int NB = n >> 8;
    int k = 0;
    while (k < n) {
        u32 cur_x = (u32)(keys[k] >> 32);
        int kk = k + 1;
        while (kk < n && (u32)(keys[kk] >> 32) == cur_x) kk++;
        for (int t = k; t < kk; ++t) {
            u32 yy = (u32)(keys[t] & 0xFFFFFFFFu);
            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[idx[t]] = s;
        }
        for (int t = k; t < kk; ++t) {
            u32 yy = (u32)(keys[t] & 0xFFFFFFFFu);
            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;
    }
}

评测结果