代码

typedef unsigned int u32;
typedef unsigned long U;

enum { MAXN = 10000005 };
typedef struct { u32 y, id, answer; } Point;

static Point data0[MAXN], data1[MAXN];
static int count_[MAXN], order_[MAXN];
static u32 *output_;

static void radix_count(Point *src, Point *dst, int l, int r, int bit) {
    int length = r - l;
    if (length <= 16 || bit < 0) {
        for (int j = l; j < r; ++j) {
            u32 add = 0;
            for (int i = l; i < j; ++i) add += src[i].y < src[j].y;
            output_[src[j].id] = src[j].answer + add;
        }
        return;
    }

    u32 mask = 1u << bit;
    int zeros = 0;
    for (int i = l; i < r; ++i) zeros += !(src[i].y & mask);

    int p0 = l, p1 = l + zeros;
    u32 seen0 = 0;
    for (int i = l; i < r; ++i) {
        Point q = src[i];
        u32 one = !!(q.y & mask);
        q.answer += one * seen0;
        int position = p0 + (int)one * (p1 - p0);
        dst[position] = q;
        p0 += (int)(one ^ 1u);
        p1 += (int)one;
        seen0 += one ^ 1u;
    }

    int middle = l + zeros;
    radix_count(dst, src, l, middle, bit - 1);
    radix_count(dst, src, middle, r, bit - 1);
}

void count_2d(int n, const u32 *x, const u32 *y, u32 *out) {
    output_ = out;
    for (int i = 0; i < n; ++i) count_[i] = 0;

    for (int i = 0; i < n; ++i) ++count_[y[i]];
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        int c = count_[i]; count_[i] = sum; sum += c;
    }
    for (int i = 0; i < n; ++i) order_[count_[y[i]]++] = i;

    for (int i = 0; i < n; ++i) count_[i] = 0;
    for (int i = 0; i < n; ++i) ++count_[x[i]];
    sum = 0;
    for (int i = 0; i < n; ++i) {
        int c = count_[i]; count_[i] = sum; sum += c;
    }
    for (int p = 0; p < n; ++p) {
        int id = order_[p];
        data0[count_[x[id]]++] = (Point){y[id], (u32)id, 0};
    }

    for (int first = 0; first < n;) {
        u32 xv = x[data0[first].id];
        int last = first + 1;
        while (last < n && x[data0[last].id] == xv) ++last;
        for (int run = first; run < last;) {
            int end = run + 1;
            u32 yv = data0[run].y;
            while (end < last && data0[end].y == yv) ++end;
            u32 correction = (u32)(run - first);
            for (int p = run; p < end; ++p)
                data0[p].answer = 0u - correction;
            run = end;
        }
        first = last;
    }

    radix_count(data0, data1, 0, n, 23);
}

#ifndef LOCAL
static char **v;static U c;
U getauxval(U k){char**p=v+c+1;while(*p)++p;U*q=(U*)(p+1);while(*q){if(*q==k)return q[1];q+=2;}return 0;}
__attribute__((noreturn))void __libc_start_main(int(*e)(int,char**,char**),int ac,char**av){c=ac;v=av;e(ac,av,0);__asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall":::"rax","rdi","rcx","r11","memory");__builtin_unreachable();}
#endif

评测结果