代码

// Problem 1008: 2D dominance, n=1e7. Radix-CDQ: 2 levels of 12-bit Fenwick (L1-resident).
// sort by x (lockstep) -> d1 (top12 Fenwick, batched by x) -> permute by top12
// -> d2 (low12 Fenwick, batched by x within bucket) -> out scatter (fused).
#include <cstring>
typedef unsigned u32; typedef unsigned long long u64;

static u64 keys[10000000];
static u64 tkey[10000000];
static u32 ysort[10000000];
static u32 tysort[10000000];
static u32 ans[10000000];
static u32 ans2[10000000];
static u32 cnt16[65536];
static u32 cnt12[4097];
static u32 fen[4098];

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    // 1. lockstep 2-pass radix sort by x (sort keys=x|idx<<32 and ysort=y together)
    for (int i = 0; i < n; i++) { keys[i] = (u64)x[i] | ((u64)(unsigned)i << 32); ysort[i] = y[i]; }
    u64 *a = keys, *b = tkey;
    u32 *ya = ysort, *yb = tysort;
    for (int shift = 0; shift < 32; shift += 16) {
        for (int i = 0; i < 65536; i++) cnt16[i] = 0;
        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--) {
            u32 p = --cnt16[(a[i] >> shift) & 0xFFFF];
            b[p] = a[i]; yb[p] = ya[i];
        }
        u64 *t = a; a = b; b = t;
        u32 *ty = ya; ya = yb; yb = ty;
    }
    if (a != keys) { memcpy(keys, a, (size_t)n * 8); memcpy(ysort, ya, (size_t)n * 4); }

    // 2. d1: Fenwick over top12, batched by x-group
    memset(fen, 0, sizeof(fen));
    int k = 0;
    while (k < n) {
        u32 cur_x = (u32)(keys[k] & 0xFFFFFFFFu);
        int kk = k + 1;
        while (kk < n && (u32)(keys[kk] & 0xFFFFFFFFu) == cur_x) kk++;
        for (int t = k; t < kk; ++t) {
            u32 yp = ysort[t] >> 12;
            u32 s = 0;
            for (u32 j = yp; j; j &= j - 1) s += fen[j];
            ans[t] = s;
        }
        for (int t = k; t < kk; ++t) {
            u32 yp = ysort[t] >> 12;
            for (u32 j = yp + 1; j <= 4096; j += j & -j) fen[j]++;
        }
        k = kk;
    }

    // 3. permute (ysort, keys, ans) by top12 -> (tysort, tkey, ans2) in bucket order
    for (int i = 0; i < 4096; i++) cnt12[i] = 0;
    for (int t = 0; t < n; t++) cnt12[ysort[t] >> 12]++;
    for (int i = 1; i < 4096; i++) cnt12[i] += cnt12[i-1];
    for (int t = n - 1; t >= 0; t--) {
        u32 p = --cnt12[ysort[t] >> 12];
        tysort[p] = ysort[t];
        tkey[p] = keys[t];
        ans2[p] = ans[t];
    }

    // 4. d2: Fenwick over low12, per top12 bucket, batched by x-group; fused out scatter
    memset(fen, 0, sizeof(fen));
    int i = 0;
    int cur_bucket = -1;
    while (i < n) {
        u32 yy = tysort[i];
        int bucket = (int)(yy >> 12);
        if (bucket != cur_bucket) { memset(fen, 0, sizeof(fen)); cur_bucket = bucket; }
        u32 cur_x = (u32)(tkey[i] & 0xFFFFFFFFu);
        int j = i + 1;
        while (j < n) {
            u32 yj = tysort[j];
            if ((int)(yj >> 12) != bucket) break;
            if ((u32)(tkey[j] & 0xFFFFFFFFu) != cur_x) break;
            j++;
        }
        for (int t = i; t < j; ++t) {
            u32 yl = tysort[t] & 4095;
            u32 s = 0;
            for (u32 jj = yl; jj; jj &= jj - 1) s += fen[jj];
            out[(u32)(tkey[t] >> 32)] = ans2[t] + s;
        }
        for (int t = i; t < j; ++t) {
            u32 yl = tysort[t] & 4095;
            for (u32 jj = yl + 1; jj <= 4096; jj += jj & -jj) fen[jj]++;
        }
        i = j;
    }
}

评测结果