代码

#include <immintrin.h>

typedef unsigned int u32;
typedef unsigned long U;

enum { MAXN = 10000005 };
static int counts[MAXN];
static int order_[MAXN];
static int cursor_[MAXN];

void count_2d(int n, const u32 *x, const u32 *y, u32 *out) {
#ifdef TRACE
    static int call; ++call;
#endif
    for (int i = 0; i < n; ++i) counts[i] = 0;
    for (int i = 0; i < n; ++i) counts[x[i]]++;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        int c = counts[i];
        counts[i] = 0;
        cursor_[i] = sum;
        sum += c;
    }

    /* Transform x rank to the Fenwick insertion position after its entire
       equal-x group.  Query before inserting a group enforces strict x. */
    for (int i = 0; i < n; ++i) order_[cursor_[x[i]]++] = i;
#ifdef TRACE
    if(n==3){for(int i=0;i<n;++i)__builtin_printf("call%d ord %d id %d x%u y%u\n",call,i,order_[i],x[order_[i]],y[order_[i]]);}
#endif

    for (int first = 0; first < n;) {
        u32 xv = x[order_[first]];
        int last = first + 1;
        while (last < n && x[order_[last]] == xv) ++last;
#ifdef TRACE
        if(n==3)__builtin_printf("grp %d %d xv%u bit1=%d bit2=%d bit3=%d\n",first,last,xv,counts[1],counts[2],counts[3]);
#endif

        for (int p = first; p < last; ++p) {
            int id = order_[p];
            u32 result = 0;
            for (int q = (int)y[id]; q; q -= q & -q)
                result += (u32)counts[q];
            out[id] = result;
        }
        for (int p = first; p < last; ++p) {
            int q = (int)y[order_[p]] + 1;
            for (; q <= n; q += q & -q) ++counts[q];
        }
        first = last;
    }
    for (int i = 0; i <= n; ++i) counts[i] = 0;
}

#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

评测结果