代码

// v6 step2: eliminate perm by scattering packed (low12|ans|idx) into bucket_buf during d1.
// Build fused into pass0, pointer-tracked sort, descending-y insertion, histogram -> d1(Fenwick+scatter) -> d2(Fenwick+out).
#include <cstring>
#pragma GCC target("bmi")
#pragma GCC optimize("O3")
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 u64 bucket_buf[10000000];
static u32 cnt[4097];
static u32 wptr[4096];
static u32 fen[4098];

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    // pass 0 fused with build
    for (int i = 0; i < 256; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) cnt[x[i] & 255]++;
    for (int i = 1; i < 256; i++) cnt[i] += cnt[i-1];
    for (int i = n - 1; i >= 0; i--) {
        u32 p = --cnt[x[i] & 255];
        tkey[p] = (u64)x[i] | ((u64)(unsigned)i << 32);
        tysort[p] = y[i];
    }
    u64 *a = tkey, *b = keys; u32 *ya = tysort, *yb = ysort;
    for (int shift = 8; 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;
    }
    u64 *kk = a; u32 *yy = ya;  // sorted keys/y in x-order

    // insertion sort descending-y within x-groups
    int k = 0;
    while (k < n) {
        u32 cx = (u32)(kk[k] & 0xFFFFFFFFu);
        int kk2 = k + 1;
        while (kk2 < n && (u32)(kk[kk2] & 0xFFFFFFFFu) == cx) kk2++;
        int g = kk2 - k;
        if (g == 2) {
            u32 y0 = yy[k], y1 = yy[k + 1];
            if (y0 < y1) { yy[k] = y1; yy[k + 1] = y0; u64 tk = kk[k]; kk[k] = kk[k + 1]; kk[k + 1] = tk; }
        } else if (g > 2) {
            for (int i = k + 1; i < kk2; i++) {
                u32 yv = yy[i]; u64 kv = kk[i];
                int j = i - 1;
                while (j >= k && yy[j] < yv) { yy[j + 1] = yy[j]; kk[j + 1] = kk[j]; j--; }
                yy[j + 1] = yv; kk[j + 1] = kv;
            }
        }
        k = kk2;
    }

    // histogram of y>>12, then bucket starts
    for (int i = 0; i < 4096; i++) cnt[i] = 0;
    for (int t = 0; t < n; t++) cnt[yy[t] >> 12]++;
    u32 total = 0;
    for (int b = 0; b < 4096; b++) { u32 s = cnt[b]; cnt[b] = total; total += s; }
    cnt[4096] = total;
    for (int b = 0; b < 4096; b++) wptr[b] = cnt[b];

    // d1: Fenwick over top12 + scatter packed (low12|ans|idx) into bucket_buf
    memset(fen, 0, sizeof(fen));
    for (int t = 0; t < n; t++) {
        u32 yv = yy[t];
        u32 yp = yv >> 12; u32 s = 0;
        for (u32 j = yp; j; j &= j - 1) s += fen[j];
        bucket_buf[wptr[yp]++] = (u64)(yv & 4095) | ((u64)s << 12) | ((u64)(kk[t] >> 32) << 36);
        for (u32 j = yp + 1; j <= 4096; j += j & -j) fen[j]++;
    }

    // d2: Fenwick over low12 per bucket, fused out scatter
    for (int b = 0; b < 4096; b++) {
        memset(fen, 0, sizeof(fen));
        for (u32 t = cnt[b]; t < cnt[b + 1]; t++) {
            u64 packed = bucket_buf[t];
            u32 yl = (u32)(packed & 4095); u32 s = 0;
            for (u32 jj = yl; jj; jj &= jj - 1) s += fen[jj];
            out[(u32)(packed >> 36)] = (u32)((packed >> 12) & 0xFFFFFF) + s;
            for (u32 jj = yl + 1; jj <= 4096; jj += jj & -jj) fen[jj]++;
        }
    }
}

评测结果