代码

// 2D dominance via merge-sort inversion counting (sequential, bandwidth-bound).
#include <cstring>
typedef unsigned u32;
typedef unsigned long long u64;

static int cntA[10000000];
static int orderY[10000000];
static int order[10000000];
static u64 kb1[10000000];
static u64 kb2[10000000];
static u32 cb1[10000000];
static u32 cb2[10000000];
static u32 d[10000000];

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    // 1. stable counting sort by y -> orderY
    for (int i = 0; i < n; ++i) cntA[y[i]]++;
    for (int i = 1; i < n; ++i) cntA[i] += cntA[i-1];
    for (int i = n-1; i >= 0; --i) orderY[--cntA[y[i]]] = i;
    // 2. stable counting sort by x over orderY -> order (sorted (x,y))
    memset(cntA, 0, n * sizeof(int));
    for (int k = 0; k < n; ++k) cntA[x[orderY[k]]]++;
    for (int i = 1; i < n; ++i) cntA[i] += cntA[i-1];
    for (int k = n-1; k >= 0; --k) order[--cntA[x[orderY[k]]]] = orderY[k];

    // 3. build key = (y<<32)|origindex, c=0
    u64 *key = kb1, *akey = kb2;
    u32 *c = cb1, *ac = cb2;
    for (int k = 0; k < n; ++k) {
        int ii = order[k];
        key[k] = ((u64)y[ii] << 32) | (u64)(unsigned)ii;
        c[k] = 0;
    }

    // 4. merge sort by value, accumulate previous-smaller
    for (int w = 1; w < n; w <<= 1) {
        for (int lo = 0; lo < n; lo += 2*w) {
            int mid = lo + w; if (mid > n) mid = n;
            int hi = lo + 2*w; if (hi > n) hi = n;
            int i = lo, j = mid, k = lo;
            while (i < mid && j < hi) {
                int take_left = ((key[i] >> 32) < (key[j] >> 32));
                akey[k] = take_left ? key[i] : key[j];
                ac[k] = take_left ? c[i] : (c[j] + (u32)(i - lo));
                i += take_left; j += (1 - take_left); k++;
            }
            while (i < mid) { akey[k] = key[i]; ac[k] = c[i]; i++; k++; }
            while (j < hi) { akey[k] = key[j]; ac[k] = c[j] + (u32)(i - lo); j++; k++; }
        }
        u64 *tk = key; key = akey; akey = tk;
        u32 *tc = c; c = ac; ac = tc;
    }

    // 5. same-x correction d[] over (x,y)-order
    {
        unsigned prev_x = 0xFFFFFFFFu, prev_y = 0;
        int p = 0, eq_run = 0;
        for (int k = 0; k < n; ++k) {
            int ii = order[k];
            unsigned xi = x[ii], yi = y[ii];
            if (xi != prev_x) { p = 0; eq_run = 0; prev_x = xi; prev_y = yi; }
            else { if (yi != prev_y) { eq_run = 0; prev_y = yi; } }
            d[ii] = (u32)(p - eq_run);
            eq_run++; p++;
        }
    }

    // 6. scatter
    for (int k = 0; k < n; ++k) {
        int ii = (int)(key[k] & 0xFFFFFFFFu);
        out[ii] = c[k] - d[ii];
    }
}

评测结果