代码

/* 1008 v1: LSD radix sort (x asc, y desc) + 6-bit-digit MSD divide&conquer
 * counting with a "chunked bitset" carry.
 *
 * After sorting by key=(x<<24)|(0xFFFFFF-y) the position order is (x asc, y desc),
 * so for element e at position p:  ans[e] = #{ f : pos_f < p, y_f < y_e }.
 * That is computed by an MSD radix recursion on the 24-bit y, 6 bits per level:
 * at each level the elements of a node are partitioned by the next 6 y-bits and
 * each element gets += (number of preceding elements *in that node* with a smaller
 * digit).  The prefix count over the 64 digit buckets is obtained from 64-bit
 * position bitsets inside each 64-element chunk:
 *     carry = pre[d] + popcount( ltm[d] & ((1<<i)-1) )
 * ltm[d] = OR of pos[0..d-1] (prefix OR within the chunk), pre[d] = prefix sum of
 * the node's digit histogram counted before the chunk.
 */
#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)

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

/* one LSD radix pass using the precomputed raw histogram h[] (destroyed),
 * optionally accumulating the histogram of digit sh+8 into nh[] */
static void radix_pass(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) {
        int sh2 = sh + 8;
        memset(nh, 0, 1024);
        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;
        }
    }
}

/* partition nb nodes (boundaries boff[]) by the digit at `shift` into nboff[],
 * adding the per-element carry */
static void level_pass(u32 nb, const u32 *boff, const E *iv, E *ov, u32 *nboff, int shift) {
    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]++;
                ov[p].k = iv[base + i].k;
                ov[p].c = iv[base + i].c + carry;
                hist[d]++;
            }
        }
    }
    nboff[(size_t)nb * KN] = gpos;
}

/* last level: only the carry is needed; write the answer straight to out[id] */
static void final_pass(u32 nb, const u32 *boff, const E *iv, u32 *out, 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));
                out[(u32)(iv[base + i].k & 0xFFFFFFu)] = iv[base + i].c + carry;
                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);
    u32 *nboff2 = (u32 *)malloc(4 * ((size_t)KN * KN + 1));
    u32 *nboff3 = (u32 *)malloc(4 * ((size_t)KN * KN * KN + 1));
    if (!a || !b || !nboff2 || !nboff3) return;

    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] << 24) | (u64)(0xFFFFFFu - y[i]);
        a[i].k = k; a[i].c = (u32)i;
        h0[k & 255u]++;
    }
    radix_pass(n, a, b, 0, h0, h1);
    radix_pass(n, b, a, 8, h1, h2);
    radix_pass(n, a, b, 16, h2, h0);
    radix_pass(n, b, a, 24, h0, h1);
    radix_pass(n, a, b, 32, h1, h2);
    /* final pass: x high byte, result in a, build val=(y<<24)|id and cnt=0 */
    {
        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 = b[i].k;
            u32 pp = h2[(u32)(k >> 40) & 255u]++;
            a[pp].k = ((u64)(0xFFFFFFu - (u32)(k & 0xFFFFFFu)) << 24) | (u64)b[i].c;
            a[pp].c = 0;
        }
    }
    /* 4 MSD levels over the 24 bits of y: 6 bits each */
    u32 boff0[2]; boff0[0] = 0; boff0[1] = (u32)n;
    u32 *nboff1 = nboff2;   /* level 0 -> 64 nodes, needs 64*64+1 entries; reuse later */
    u32 *tmp = (u32 *)malloc(4 * (KN + 1));
    (void)nboff1;
    level_pass(1, boff0, a, b, tmp, 42);
    level_pass(KN, tmp, b, a, nboff2, 36);
    level_pass(KN * KN, nboff2, a, b, nboff3, 30);
    final_pass(KN * KN * KN, nboff3, b, out, 24);
    free(a); free(b); free(nboff2); free(nboff3); free(tmp);
}

评测结果