代码

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)x[i] << 32 | 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; b[k] >> 32 == i; k++) {
            u32 id = b[i];
            out[id] = tree.sum(y[id]);
        }
        for(; b[j] >> 32 == i; j++) {
            u32 id = b[i];
            tree.add(y[id]);
        }
    }
}

评测结果