代码

#include <immintrin.h>
typedef unsigned u32;typedef unsigned long u64;typedef unsigned long U;
#ifndef CAPACITY
#define CAPACITY 300005
#endif
#ifndef BLOCK_SIZE
#define BLOCK_SIZE 128
#endif
enum{N=CAPACITY,B=BLOCK_SIZE,W=(N+63)/64,NB=(N+B-1)/B+1};
static int order[N],sd[3][N],cnt[N],st[N],rp[3][N],lo[3][N],seen[N];
static u64 active[3][W],cur[W],pre[6][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 sortdim(int d,int n,const u32*x){__builtin_memset(cnt,0,(unsigned)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]];}}
static void build(int ix,int d,int a,int n,int words){__builtin_memset(cur,0,(unsigned)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=rp[a][id];cur[q>>6]|=1ul<<(q&63);}__builtin_memcpy(pre[ix][b],cur,(unsigned)words*8);}}
__attribute__((target("popcnt")))void count_4d(int n,const u32*x[4],u32*out){int words=(n+63)>>6;for(int a=0;a<3;++a)__builtin_memset(active[a],0,(unsigned)words*8);__builtin_memset(seen,0,(unsigned)n*4);for(int d=0;d<3;++d)sortdim(d,n,x[d+1]);build(0,1,0,n,words);build(1,2,0,n,words);build(2,0,1,n,words);build(3,2,1,n,words);build(4,0,2,n,words);build(5,1,2,n,words);
 __builtin_memset(cnt,0,(unsigned)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],a=lo[1][id]<lo[0][id];if(lo[2][id]<lo[a][id])a=2;int d0=a?0:1,d1=a==2?1:2,lim=lo[a][id],l0=lo[d0][id],l1=lo[d1][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;int ix0=a*2,ix1=ix0+1;u64*p0=pre[ix0][b0],*p1=pre[ix1][b1],*aa=active[a];u32 res=pc(lim>>6,aa,p0,p1);int rem=lim&63;if(rem)res+=__builtin_popcountll(aa[lim>>6]&p0[lim>>6]&p1[lim>>6]&((1ul<<rem)-1));++stamp;for(int k=0;k<2;++k){int d=k?d1:d0,l=k?l1:l0,ee=k?e1:e0;for(int p=l;p<ee;++p){int q=sd[d][p];if(seen[q]==stamp)continue;seen[q]=stamp;int bit=rp[a][q];if(bit<lim&&((aa[bit>>6]>>(bit&63))&1)&&rp[d0][q]<e0&&rp[d1][q]<e1)--res;}}out[id]=res;}for(int p=f;p<e;++p){int id=order[p];for(int a=0;a<3;++a){int q=rp[a][id];active[a][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

评测结果