代码

#include <immintrin.h>
typedef unsigned u32;typedef unsigned long u64;typedef unsigned long U;
#ifndef BLOCK_SIZE
#define BLOCK_SIZE 16
#endif
enum{N=100005,B=BLOCK_SIZE,W=(N+63)/64,NB=(N+B-1)/B+1};
static int order[N],sd[2][N],cnt[N],st[N],r0[N],lo0[N],rp[2][N],lo[2][N],seen[N];
static u64 active[W],cur[W],pre[2][NB][W];

__attribute__((target("popcnt"),always_inline))static inline u32 pc(int words,const u64*a,const u64*b,const u64*c){
 u64 s0=0,s1=0,s2=0,s3=0,s4=0,s5=0,s6=0,s7=0;int i=0;
 for(;i+8<=words;i+=8){
  s0+=__builtin_popcountll(a[i]&b[i]&c[i]);s1+=__builtin_popcountll(a[i+1]&b[i+1]&c[i+1]);
  s2+=__builtin_popcountll(a[i+2]&b[i+2]&c[i+2]);s3+=__builtin_popcountll(a[i+3]&b[i+3]&c[i+3]);
  s4+=__builtin_popcountll(a[i+4]&b[i+4]&c[i+4]);s5+=__builtin_popcountll(a[i+5]&b[i+5]&c[i+5]);
  s6+=__builtin_popcountll(a[i+6]&b[i+6]&c[i+6]);s7+=__builtin_popcountll(a[i+7]&b[i+7]&c[i+7]);
 }
 for(;i<words;++i)s0+=__builtin_popcountll(a[i]&b[i]&c[i]);return(u32)(s0+s1+s2+s3+s4+s5+s6+s7);
}
static void sort0(int n,const u32*x){__builtin_memset(cnt,0,n*4);for(int i=0;i<n;++i)++cnt[x[i]];int z=0;for(int q=0;q<n;++q){int t=cnt[q];st[q]=z;cnt[q]=z;z+=t;}for(int i=0;i<n;++i){int p=cnt[x[i]]++;r0[i]=p;lo0[i]=st[x[i]];}}
static void build(int d,int n,int words,const u32*x){__builtin_memset(cnt,0,n*4);for(int i=0;i<n;++i)++cnt[x[i]];int z=0;for(int q=0;q<n;++q){int t=cnt[q];st[q]=z;cnt[q]=z;z+=t;}for(int i=0;i<n;++i){int p=cnt[x[i]]++;sd[d][p]=i;rp[d][i]=p;lo[d][i]=st[x[i]];}__builtin_memset(cur,0,words*8);int blocks=(n+B-1)/B;for(int b=1;b<=blocks;++b){int e=b*B;if(e>n)e=n;for(int p=(b-1)*B;p<e;++p){int id=sd[d][p],q=r0[id];cur[q>>6]|=1ul<<(q&63);}__builtin_memcpy(pre[d][b],cur,words*8);}}
__attribute__((target("popcnt")))void count_4d(int n,const u32*x[4],u32*out){int words=(n+63)>>6;__builtin_memset(active,0,words*8);__builtin_memset(seen,0,n*4);sort0(n,x[1]);build(0,n,words,x[2]);build(1,n,words,x[3]);
 __builtin_memset(cnt,0,n*4);for(int i=0;i<n;++i)++cnt[x[0][i]];int z=0;for(int q=0;q<n;++q){int t=cnt[q];cnt[q]=z;z+=t;}for(int i=0;i<n;++i)order[cnt[x[0][i]]++]=i;
 int stamp=0;for(int f=0;f<n;){int e=f+1;u32 xv=x[0][order[f]];while(e<n&&x[0][order[e]]==xv)++e;for(int qi=f;qi<e;++qi){int id=order[qi],lim=lo0[id],l0=lo[0][id],l1=lo[1][id],b0=(l0+B-1)/B,b1=(l1+B-1)/B,e0=b0*B,e1=b1*B;if(e0>n)e0=n;if(e1>n)e1=n;u32 res=pc(lim>>6,active,pre[0][b0],pre[1][b1]);int rem=lim&63;if(rem)res+=__builtin_popcountll(active[lim>>6]&pre[0][b0][lim>>6]&pre[1][b1][lim>>6]&((1ul<<rem)-1));++stamp;for(int d=0;d<2;++d){int l=d?l1:l0,ee=d?e1:e0;for(int p=l;p<ee;++p){int q=sd[d][p];if(seen[q]==stamp)continue;seen[q]=stamp;int bit=r0[q];if(bit<lim&&((active[bit>>6]>>(bit&63))&1)&&rp[0][q]<e0&&rp[1][q]<e1)--res;}}out[id]=res;}for(int p=f;p<e;++p){int id=order[p],q=r0[id];active[q>>6]|=1ul<<(q&63);}f=e;}
}
#ifndef LOCAL
static char**v;static U ac_;U getauxval(U k){char**p=v+ac_+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){ac_=ac;v=av;e(ac,av,0);__asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall":::"rax","rdi","rcx","r11","memory");__builtin_unreachable();}
#endif

评测结果