代码

/* 1008 v4: 3-pass LSD radix sort on x only (carrying y and the high id bits inside
 * the 12-byte element), a within-x-group correction pass, then the 6-bit MSD
 * divide&conquer counting over y, and finally an id-bucketed (localised) scatter.
 *
 * Elements are packed E = { u64 k = (x:24 << 40) | (y:24 << 16) | (id & 0xFFFF),
 *                           u32 c = id >> 16 }.
 * Sorting is stable, so inside an x-group the original input order is kept:
 *   #{f before e in position order, y_f<y_e} = ans_e + #{f same x-group, earlier, y_f<y_e}
 * so the second term is subtracted by initialising cnt = -correction.
 */
#include <stdlib.h>
#include <string.h>

#pragma GCC target("popcnt")

typedef unsigned u32;
typedef unsigned long long u64;
typedef unsigned char u8;

#define KDIG 6
#define KN (1 << KDIG)
#define IDB 6                 /* id buckets for the final localised scatter */
#define IDN (1 << IDB)

struct __attribute__((packed)) E { u64 k; u32 c; };

/* ---------- LSD radix pass over the x digits (bits 40..63 of k) ---------- */
static void xpass(int n, const E *a, E *b, int sh, u32 *h, u32 *nh) {
    u32 s = 0;
    for (int d = 0; d < 256; d++) { u32 c = h[d]; h[d] = s; s += c; }
    if (nh) {
        memset(nh, 0, 1024);
        int sh2 = sh + 8;
        for (int i = 0; i < n; i++) {
            u64 k = a[i].k;
            u32 pp = h[(u32)(k >> sh) & 255u]++;
            b[pp].k = k; b[pp].c = a[i].c;
            nh[(u32)(k >> sh2) & 255u]++;
        }
    } else {
        for (int i = 0; i < n; i++) {
            u64 k = a[i].k;
            u32 pp = h[(u32)(k >> sh) & 255u]++;
            b[pp].k = k; b[pp].c = a[i].c;
        }
    }
}

/* ---------- one MSD level: partition by 6 y-bits, add the carries ---------- */
static void level_pass(u32 nb, const u32 *boff, const E *iv, E *ov, u32 *nboff, int shift, u32 *idhist) {
    u32 gpos = 0;
    for (u32 j = 0; j < nb; j++) {
        u32 lo = boff[j], hi = boff[j + 1];
        if (lo >= hi) {
            for (int d = 0; d < KN; d++) nboff[(size_t)j * KN + d] = gpos;
            continue;
        }
        u32 off[KN], hist[KN];
        memset(hist, 0, sizeof(hist));
        for (u32 i = lo; i < hi; i++) hist[(u32)(iv[i].k >> shift) & (KN - 1)]++;
        for (int d = 0; d < KN; d++) { off[d] = gpos; nboff[(size_t)j * KN + d] = gpos; gpos += hist[d]; }
        memset(hist, 0, sizeof(hist));
        for (u32 base = lo; base < hi; base += 64) {
            u32 c = hi - base; if (c > 64) c = 64;
            u64 pos[KN], ltm[KN];
            u32 pre[KN];
            u8 dig[64];
            for (int d = 0; d < KN; d++) pos[d] = 0;
            u64 bit = 1;
            for (u32 i = 0; i < c; i++) {
                u32 d = (u32)(iv[base + i].k >> shift) & (KN - 1);
                dig[i] = (u8)d; pos[d] |= bit; bit <<= 1;
            }
            { u64 acc = 0; for (int d = 0; d < KN; d++) { u64 t = acc; acc |= pos[d]; ltm[d] = t; } }
            { u32 acc = 0; for (int d = 0; d < KN; d++) { pre[d] = acc; acc += hist[d]; } }
            for (u32 i = 0; i < c; i++) {
                u32 d = dig[i];
                u32 carry = pre[d] + (u32)__builtin_popcountll(ltm[d] & ((1ull << i) - 1));
                u32 p = off[d]++;
                u64 kk = iv[base + i].k;
                ov[p].k = kk;
                ov[p].c = iv[base + i].c + carry;
                if (idhist) idhist[(u32)(kk & 0xFFFFFFu) >> (24 - IDB)]++;
                hist[d]++;
            }
        }
    }
    nboff[(size_t)nb * KN] = gpos;
}

/* ---------- last level: carry + partition the (id,count) pairs by id-bucket ---------- */
static void final_pass(u32 nb, const u32 *boff, const E *iv, u64 *ov, u32 *o, int shift) {
    for (u32 j = 0; j < nb; j++) {
        u32 lo = boff[j], hi = boff[j + 1];
        if (lo >= hi) continue;
        u32 hist[KN];
        memset(hist, 0, sizeof(hist));
        for (u32 base = lo; base < hi; base += 64) {
            u32 c = hi - base; if (c > 64) c = 64;
            u64 pos[KN], ltm[KN];
            u32 pre[KN];
            u8 dig[64];
            for (int d = 0; d < KN; d++) pos[d] = 0;
            u64 bit = 1;
            for (u32 i = 0; i < c; i++) {
                u32 d = (u32)(iv[base + i].k >> shift) & (KN - 1);
                dig[i] = (u8)d; pos[d] |= bit; bit <<= 1;
            }
            { u64 acc = 0; for (int d = 0; d < KN; d++) { u64 t = acc; acc |= pos[d]; ltm[d] = t; } }
            { u32 acc = 0; for (int d = 0; d < KN; d++) { pre[d] = acc; acc += hist[d]; } }
            for (u32 i = 0; i < c; i++) {
                u32 d = dig[i];
                u32 carry = pre[d] + (u32)__builtin_popcountll(ltm[d] & ((1ull << i) - 1));
                u32 id = (u32)(iv[base + i].k & 0xFFFFFFu);
                ov[o[id >> (24 - IDB)]++] = (u64)id | ((u64)(iv[base + i].c + carry) << 24);
                hist[d]++;
            }
        }
    }
}

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    if (n <= 0) return;
    if (n == 1) { out[0] = 0; return; }
    E *a = (E *)malloc(12 * (size_t)n);
    E *b = (E *)malloc(12 * (size_t)n);
    u64 *pairs = 0;
    u32 *nboff2 = (u32 *)malloc(4 * ((size_t)KN * KN + 1));
    u32 *nboff3 = (u32 *)malloc(4 * ((size_t)KN * KN * KN + 1));
    u32 *tmp = (u32 *)malloc(4 * (KN + 1));
    u32 *idoff = (u32 *)malloc(4 * (IDN + 1));
    if (!a || !b || !nboff2 || !nboff3 || !tmp || !idoff) return;
    pairs = (u64 *)a;   /* "a" is free after the D&C levels; reuse it for the pairs array */

    /* ---- init: pack + histogram of the top x byte ---- */
    u32 h0[256], h1[256], h2[256];
    memset(h0, 0, sizeof(h0)); memset(h1, 0, sizeof(h1)); memset(h2, 0, sizeof(h2));
    for (int i = 0; i < n; i++) {
        u64 k = ((u64)x[i] << 40) | ((u64)y[i] << 16) | ((u32)i & 0xFFFFu);
        a[i].k = k; a[i].c = (u32)i >> 16;
        h0[(u32)(k >> 40) & 255u]++;
    }
    xpass(n, a, b, 40, h0, h1);
    xpass(n, b, a, 48, h1, h2);
    /* last x pass: also build val=(y<<24)|id and the correction term cnt=-corr */
    {
        u32 s = 0;
        for (int d = 0; d < 256; d++) { u32 c = h2[d]; h2[d] = s; s += c; }
        for (int i = 0; i < n; i++) {
            u64 k = a[i].k;
            u32 pp = h2[(u32)(k >> 56) & 255u]++;
            b[pp].k = k; b[pp].c = a[i].c;
        }
    }
    /* ---- correction + build: b (x-sorted) -> a (val=(y<<24)|id, cnt=-corr) ---- */
    {
        int i = 0;
        while (i < n) {
            u32 xv = (u32)(b[i].k >> 40);
            int j = i + 1;
            while (j < n && (u32)(b[j].k >> 40) == xv) j++;
            int g = j - i;
            if (g <= 16) {
                u32 ys[16];
                for (int p = 0; p < g; p++) ys[p] = (u32)(b[i + p].k >> 16) & 0xFFFFFFu;
                for (int p = 0; p < g; p++) {
                    u32 corr = 0;
                    for (int q = 0; q < p; q++) if (ys[q] < ys[p]) corr++;
                    u32 id = (u32)(b[i + p].k & 0xFFFFu) | (b[i + p].c << 16);
                    a[i + p].k = ((u64)ys[p] << 24) | id;
                    a[i + p].c = 0u - corr;
                }
            } else {
                /* sort the group by y ascending: LSD over y bytes, b -> a -> b -> a */
                u32 hh[3][256];
                memset(hh, 0, sizeof(hh));
                for (int p = i; p < j; p++) {
                    u32 yy = (u32)(b[p].k >> 16) & 0xFFFFFFu;
                    hh[0][yy & 255u]++; hh[1][(yy >> 8) & 255u]++; hh[2][(yy >> 16) & 255u]++;
                }
                E *src = b + i, *dst = a + i;
                for (int pass = 0; pass < 3; pass++) {
                    u32 *h = hh[pass];
                    u32 ss = 0;
                    for (int d = 0; d < 256; d++) { u32 c = h[d]; h[d] = ss; ss += c; }
                    for (int p = 0; p < g; p++) {
                        u32 yy = (u32)(src[p].k >> 16) & 0xFFFFFFu;
                        u32 q = h[(yy >> (8 * pass)) & 255u]++;
                        dst[q].k = src[p].k; dst[q].c = src[p].c;
                    }
                    E *t = src; src = dst; dst = t;
                }
                /* src == a+i holds the y-sorted group; run-start correction */
                for (int p = 0; p < g; ) {
                    u32 yv = (u32)(src[p].k >> 16) & 0xFFFFFFu;
                    int q = p + 1;
                    while (q < g && ((u32)(src[q].k >> 16) & 0xFFFFFFu) == yv) q++;
                    for (int t = p; t < q; t++) {
                        u32 id = (u32)(src[t].k & 0xFFFFu) | (src[t].c << 16);
                        src[t].k = ((u64)yv << 24) | id;
                        src[t].c = 0u - (u32)p;
                    }
                    p = q;
                }
            }
            i = j;
        }
    }
    /* ---- MSD counting levels ---- */
    u32 boff0[2]; boff0[0] = 0; boff0[1] = (u32)n;
    level_pass(1, boff0, a, b, tmp, 42, 0);
    level_pass(KN, tmp, b, a, nboff2, 36, 0);
    for (int d = 0; d <= IDN; d++) idoff[d] = 0;
    level_pass(KN * KN, nboff2, a, b, nboff3, 30, idoff);
    {
        u32 ss = 0;
        for (int d = 0; d < IDN; d++) { u32 c = idoff[d]; idoff[d] = ss; ss += c; }
        idoff[IDN] = ss;
    }
    final_pass(KN * KN * KN, nboff3, b, pairs, idoff, 24);
    for (int p = 0; p < n; p++) {
        u64 v = pairs[p];
        out[(u32)(v & 0xFFFFFFu)] = (u32)(v >> 24);
    }
    free(a); free(b); free(nboff2); free(nboff3); free(tmp); free(idoff);
}

评测结果