代码

#include <stdio.h>
#define LOCAL
#define count_2d slow_count_2d
typedef unsigned int u32;
typedef unsigned long U;

enum {
    MAXN = 10000005,
    SUB_SIZE = 16,
    BLOCK_SIZE = 256,
    MAX_SUB = (MAXN + SUB_SIZE - 1) / SUB_SIZE,
    MAX_BLOCK = (MAXN + BLOCK_SIZE - 1) / BLOCK_SIZE + 1
};

static int head[MAXN], next_[MAXN];
static u32 exact_count[MAXN], sub_count[MAX_SUB], block_bit[MAX_BLOCK];

static __attribute__((always_inline)) inline u32 prefix_count(u32 y) {
    u32 result = 0;
    for (u32 i = y >> 8; i; i &= i - 1) result += block_bit[i];

    u32 sub_begin = (y >> 8) << 4;
    u32 sub_end = y >> 4;
    for (u32 i = sub_begin; i < sub_end; ++i) result += sub_count[i];

    u32 exact_begin = y & ~15u;
    for (u32 i = exact_begin; i < y; ++i) result += exact_count[i];
    return result;
}

static __attribute__((always_inline)) inline void insert_y(int block_count,
                                                            u32 y) {
    ++exact_count[y];
    ++sub_count[y >> 4];
    for (int i = (int)(y >> 8) + 1; i <= block_count; i += i & -i)
        ++block_bit[i];
}

void count_2d(int n, const u32 *x, const u32 *y, u32 *out) {
#ifdef LOCAL
    for (int i = 0; i < n; ++i) head[i] = 0, exact_count[i] = 0;
    for (int i = 0; i < (n + SUB_SIZE - 1) / SUB_SIZE; ++i)
        sub_count[i] = 0;
    for (int i = 0; i <= (n + BLOCK_SIZE - 1) / BLOCK_SIZE; ++i)
        block_bit[i] = 0;
#endif
    for (int i = 0; i < n; ++i) {
        u32 xv = x[i];
        next_[i] = head[xv];
        head[xv] = i + 1;
    }

    int block_count = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;
    for (int xv = 0; xv < n; ++xv) {
        int link = head[xv];
        for (int p = link; p; p = next_[p - 1]) {
            int id = p - 1;
            out[id] = prefix_count(y[id]);
        }
        for (int p = link; p; p = next_[p - 1]) {
            int id = p - 1;
            insert_y(block_count, y[id]);
        }
    }
}

#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
#undef count_2d
#undef LOCAL
typedef unsigned long U;
void count_2d(int n,const unsigned*x,const unsigned*y,unsigned*out){
    for(int i=0;i<64;++i)printf("P%d=%u,%u\n",i,x[i],y[i]);
    slow_count_2d(n,x,y,out);
}
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();}

评测结果