代码

template<class T> struct vector_int {};
#define vector_int(T) template <> struct vector_int<T> { using type = __attribute((vector_size(32))) T; };
vector_int(char) vector_int(short) vector_int(int) vector_int(long) vector_int(long long)
#undef vector_int

template<class T, int N, class = typename vector_int<T>::type> struct btree_sum {
    using vec = typename vector_int<T>::type;

    static constexpr int B = 64 / sizeof(T), b = __builtin_ctz(B);

    static constexpr int height(int n) {
        return n <= B ? 1 : height(n >> b) + 1;
    }
    static constexpr int offset(int h) {
        int s = 0, n = N;
        while(h--) s += (n + B - 1) & -B, n = (n + B - 1) >> b;
        return s;
    }
    static constexpr int H = height(N);

    struct precalc {
        T mask[B][B];
        int offset_v[H];
        constexpr precalc() :mask{}, offset_v{} {
            for(int i = 0; i < B; i++)
                for(int j = i + 1; j < B; j++) mask[i][j] = -1;
            for(int i = 0; i < H; i++) offset_v[i] = offset(i);
        }
    };
    static constexpr auto p = precalc();
    T a[offset(H)];
    inline T sum(unsigned k) {
        T s = 0;
        #pragma GCC unroll 64
        for(int h = 0; h < H; h++)
            s += a[p.offset_v[h] + (k >> (h * b))];
        return s;
    }
    inline void add(unsigned k) {
        const auto v = 1 + vec{};
        #pragma GCC unroll 64
        for(int h = 0; h < H; h++) {
            auto t = (vec*)&a[p.offset_v[h] + (k >> (h * b) & -B)];
            auto m = (vec*)p.mask[k >> (h * b) & (B - 1)];
            t[0] += v & m[0], t[1] += v & m[1];
        }
    }
};

using u32 = unsigned;
using u64 = unsigned long long;

const int N = 1e7 + 8;

btree_sum<int, N> tree;

u64 a[N], b[N];

void count_2d(int n, const u32* x, const u32* y, u32* out) {
    u32 buc[3][256] = {};
    #define GET(i, k) buc[k][i >> (k * 8) & 255]
    for(int i = 0; i < n; i++) {
        a[i] = (u64)i << 32 | x[i];
        GET(x[i], 0)++, GET(x[i], 1)++, GET(x[i], 2)++;
    }
    for(int k = 0; k < 3; k++) {
        u32 s = 0;
        for(int i = 0; i < 256; i++) {
            u32 t = buc[k][i];
            buc[k][i] = s, s += t;
        }
    }
    for(int i = 0; i < n; i++) b[GET(a[i], 0)++] = a[i];
    for(int i = 0; i < n; i++) a[GET(b[i], 1)++] = b[i];
    for(int i = 0; i < n; i++) b[GET(a[i], 2)++] = a[i];
    int j = 0;
    b[n] = -1;
    for(int i = 0; i < n; i++) {
        for(int k = j; (u32)b[k] == i; k++) {
            u32 id = b[k] >> 32;
            out[id] = tree.sum(y[id]);
        }
        for(; (u32)b[j] == i; j++) {
            u32 id = b[j] >> 32;
            tree.add(y[id]);
        }
    }
}

评测结果