代码

// Probe: 2-level Fenwick in natural order (WRONG, just measures time).
typedef unsigned u32;
static u32 topFen[40000];
static u32 botFen[10001000];
void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    (void)x;
    int NB = n >> 8;
    for (int i = 0; i < n; ++i) {
        u32 yy = y[i]; u32 b = yy >> 8, c = yy & 255;
        u32 s = 0;
        for (u32 j = b; j; j &= j-1) s += topFen[j];
        u32 base = b << 8;
        for (u32 j = c; j; j &= j-1) s += botFen[base+j];
        out[i] = s;
        for (u32 j = c+1; j <= 256; j += j&-j) botFen[base+j]++;
        for (u32 j = b+1; j <= (u32)NB; j += j&-j) topFen[j]++;
    }
}

评测结果