代码

// Problem 1008: 2D dominance, n=1e7. Radix-CDQ v3: 8-bit lockstep sort + 2-pass perm.
#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 cnt[4097];
static u32 fen[4098];

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    // 1. 8-bit lockstep sort by x (3 passes)
    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 < 24; shift += 8) {
        for (int i = 0; i < 256; i++) cnt[i] = 0;
        for (int i = 0; i < n; i++) cnt[(a[i] >> shift) & 255]++;
        for (int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
        for (int i = n - 1; i >= 0; i--) { u32 p = --cnt[(a[i] >> shift) & 255]; 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 cx = (u32)(keys[k] & 0xFFFFFFFFu);
        int kk = k + 1;
        while (kk < n && (u32)(keys[kk] & 0xFFFFFFFFu) == cx) 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. 2-pass perm by top12 (8-bit then 4-bit)
    for (int i = 0; i < 256; i++) cnt[i] = 0;
    for (int t = 0; t < n; t++) cnt[(ysort[t] >> 12) & 255]++;
    for (int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
    for (int t = n - 1; t >= 0; t--) { u32 p = --cnt[(ysort[t] >> 12) & 255]; tysort[p] = ysort[t]; tkey[p] = keys[t]; ans2[p] = ans[t]; }
    for (int i = 0; i < 16; i++) cnt[i] = 0;
    for (int t = 0; t < n; t++) cnt[(tysort[t] >> 20) & 15]++;
    for (int i = 1; i < 16; i++) cnt[i] += cnt[i-1];
    for (int t = n - 1; t >= 0; t--) { u32 p = --cnt[(tysort[t] >> 20) & 15]; ysort[p] = tysort[t]; keys[p] = tkey[t]; ans[p] = ans2[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 cb = -1;
    while (i < n) {
        u32 yy = ysort[i];
        int bucket = (int)(yy >> 12);
        if (bucket != cb) { memset(fen, 0, sizeof(fen)); cb = bucket; }
        u32 cx = (u32)(keys[i] & 0xFFFFFFFFu);
        int j = i + 1;
        while (j < n) {
            u32 yj = ysort[j];
            if ((int)(yj >> 12) != bucket) break;
            if ((u32)(keys[j] & 0xFFFFFFFFu) != cx) break;
            j++;
        }
        for (int t = i; t < j; ++t) {
            u32 yl = ysort[t] & 4095; u32 s = 0;
            for (u32 jj = yl; jj; jj &= jj - 1) s += fen[jj];
            out[(u32)(keys[t] >> 32)] = ans[t] + s;
        }
        for (int t = i; t < j; ++t) {
            u32 yl = ysort[t] & 4095;
            for (u32 jj = yl + 1; jj <= 4096; jj += jj & -jj) fen[jj]++;
        }
        i = j;
    }
}

评测结果