代码

typedef unsigned u32;typedef unsigned long U;
#ifndef CAPACITY
#define CAPACITY 300005
#endif
enum{N=CAPACITY};
typedef struct{u32 a,b,c,d,id;}P;
typedef struct{u32 b,c,d,id;int type;}E;
static P p[N],pt[N];static E ev[2*N],et[2*N];static int fw[N],touched[N],nt;static u32*out_;
static __attribute__((always_inline))inline void add(int n,u32 x){for(int k=x+1;k<=n;k+=k&-k){if(!fw[k])touched[nt++]=k;++fw[k];}}
static __attribute__((always_inline))inline u32 ask(u32 x){u32 z=0;for(int k=x;k;k&=k-1)z+=fw[k];return z;}
static void sortc(int l,int r){if(r-l<=1)return;int m=(l+r)>>1;sortc(l,m);sortc(m,r);int i=l,j=m,k=l;while(i<m&&j<r)et[k++]=ev[i].c<=ev[j].c?ev[i++]:ev[j++];while(i<m)et[k++]=ev[i++];while(j<r)et[k++]=ev[j++];for(i=l;i<r;++i)ev[i]=et[i];}
static void cdq3(int n,int l,int r){if(r-l<=1)return;if(ev[l].b==ev[r-1].b){sortc(l,r);return;}int m=(l+r)>>1;u32 q=ev[m].b;while(m>l&&ev[m-1].b==q)--m;if(m==l){m=(l+r)>>1;q=ev[m-1].b;while(m<r&&ev[m].b==q)++m;}cdq3(n,l,m);cdq3(n,m,r);int i=l;nt=0;for(int j=m;j<r;++j){while(i<m&&ev[i].c<ev[j].c){if(!ev[i].type)add(n,ev[i].d);++i;}if(ev[j].type)out_[ev[j].id]+=ask(ev[j].d);}for(int k=0;k<nt;++k)fw[touched[k]]=0;i=l;int j=m,k=l;while(i<m&&j<r)et[k++]=ev[i].c<=ev[j].c?ev[i++]:ev[j++];while(i<m)et[k++]=ev[i++];while(j<r)et[k++]=ev[j++];for(i=l;i<r;++i)ev[i]=et[i];}
static void sortb(int l,int r){if(r-l<=1)return;int m=(l+r)>>1;sortb(l,m);sortb(m,r);int i=l,j=m,k=l;while(i<m&&j<r)pt[k++]=p[i].b<=p[j].b?p[i++]:p[j++];while(i<m)pt[k++]=p[i++];while(j<r)pt[k++]=p[j++];for(i=l;i<r;++i)p[i]=pt[i];}
static void cdq4(int n,int l,int r){if(r-l<=1)return;if(p[l].a==p[r-1].a){sortb(l,r);return;}int m=(l+r)>>1;u32 q=p[m].a;while(m>l&&p[m-1].a==q)--m;if(m==l){m=(l+r)>>1;q=p[m-1].a;while(m<r&&p[m].a==q)++m;}cdq4(n,l,m);cdq4(n,m,r);int i=l,j=m,k=0;while(i<m&&j<r){if(p[i].b<=p[j].b){P z=p[i++];ev[k++]=(E){z.b,z.c,z.d,z.id,0};}else{P z=p[j++];ev[k++]=(E){z.b,z.c,z.d,z.id,1};}}while(i<m){P z=p[i++];ev[k++]=(E){z.b,z.c,z.d,z.id,0};}while(j<r){P z=p[j++];ev[k++]=(E){z.b,z.c,z.d,z.id,1};}cdq3(n,0,k);i=l;j=m;k=l;while(i<m&&j<r)pt[k++]=p[i].b<=p[j].b?p[i++]:p[j++];while(i<m)pt[k++]=p[i++];while(j<r)pt[k++]=p[j++];for(i=l;i<r;++i)p[i]=pt[i];}
void count_4d(int n,const u32*x[4],u32*out){out_=out;static int cnt[N],at[N];for(int i=0;i<n;++i)cnt[i]=out[i]=fw[i+1]=0;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)at[cnt[x[0][i]]++]=i;for(int i=0;i<n;++i){int id=at[i];p[i]=(P){x[0][id],x[1][id],x[2][id],x[3][id],id};}cdq4(n,0,n);}
#ifndef LOCAL
static char**v;static U ac_;U getauxval(U k){char**s=v+ac_+1;while(*s)++s;U*q=(U*)(s+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

评测结果