代码

typedef unsigned int u32;
typedef unsigned long U;

enum { MAXN = 10000005 };

typedef struct {
    u32 y;
    u32 id;
    u32 answer;
} Point;

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

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

    /* Stable y sort, then stable x sort: (x,y) order in two linear passes. */
    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};
    }

    /* Correct away same-x pairs that a plain prefix inversion count sees.
       Each x group is already sorted by y. */
    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;
    }

    Point *src = data0, *dst = data1;
    for (int width = 1; width < n; width <<= 1) {
        int step = width << 1;
        for (int l = 0; l < n; l += step) {
            int mid = l + width;
            int r = l + step;
            if (mid > n) mid = n;
            if (r > n) r = n;
            if (mid == r) {
                for (int p = l; p < r; ++p) dst[p] = src[p];
                continue;
            }

            int i = l, j = mid, k = l;
            u32 less = 0, equal_left = 0;
            u32 right_value = src[j].y;
            while (i < mid && j < r) {
                u32 rv = src[j].y;
                if (rv != right_value) {
                    less += equal_left;
                    equal_left = 0;
                    right_value = rv;
                }
                u32 lv = src[i].y;
                if (lv <= rv) {
                    if (lv < rv) ++less;
                    else ++equal_left;
                    dst[k++] = src[i++];
                } else {
                    Point q = src[j++];
                    q.answer += less;
                    dst[k++] = q;
                }
            }
            while (j < r) {
                u32 rv = src[j].y;
                if (rv != right_value) {
                    less += equal_left;
                    equal_left = 0;
                    right_value = rv;
                }
                Point q = src[j++];
                q.answer += less;
                dst[k++] = q;
            }
            while (i < mid) dst[k++] = src[i++];
        }
        Point *swap = src; src = dst; dst = swap;
    }

    for (int i = 0; i < n; ++i) out[src[i].id] = src[i].answer;
}

#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

评测结果