传送门
Solution
具体实现参考上一篇Blog（四维偏序）
代码实现1（cdq+cdq+cdq+BIT）
/*
mail: mleautomaton@foxmail.com
author: MLEAutoMaton
This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
int f=1,sum=0;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
const int N=50010;
struct node
{
int opt1,opt2,a,b,c,d;
}a[N],tmp1[N],tmp2[N],tmp3[N];
int c[N],n,tot,ans;
int lowbit(int x){return x&(-x);}
void Add(int x,int d){while(x<=n){c[x]+=d;x+=lowbit(x);}}
int query(int x){int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}
void cdq1(int,int);
void cdq2(int,int);
void cdq3(int,int);
int main()
{
n=gi();
for(int i=1;i<=n;i++)a[i].a=gi();
for(int i=1;i<=n;i++)a[i].b=gi();
for(int i=1;i<=n;i++)a[i].c=gi();
for(int i=1;i<=n;i++)a[i].d=gi();
cdq1(1,n);
printf("%d
",ans);
return 0;
}
void cdq1(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
cdq1(l,mid);cdq1(mid+1,r);
int L=l,R=mid+1;tot=l-1;
while(L<=mid && R<=r)
{
if(a[L].a<a[R].a){a[L].opt1=0;tmp1[++tot]=a[L++];}
else{a[R].opt1=1;tmp1[++tot]=a[R++];}
}
while(L<=mid){a[L].opt1=0;tmp1[++tot]=a[L++];}
while(R<=r){a[R].opt1=1;tmp1[++tot]=a[R++];}
for(int i=l;i<=r;i++)a[i]=tmp1[i];
cdq2(l,r);
}
void cdq2(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
cdq2(l,mid);cdq2(mid+1,r);
int L=l,R=mid+1;tot=l-1;
while(L<=mid && R<=r)
{
if(tmp1[L].b<tmp1[R].b){tmp1[L].opt2=0;tmp2[++tot]=tmp1[L++];}
else{tmp1[R].opt2=1;tmp2[++tot]=tmp1[R++];}
}
while(L<=mid){tmp1[L].opt2=0;tmp2[++tot]=tmp1[L++];}
while(R<=r){tmp1[R].opt2=1;tmp2[++tot]=tmp1[R++];}
for(int i=l;i<=r;i++)tmp1[i]=tmp2[i];
cdq3(l,r);
}
void cdq3(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
cdq3(l,mid);cdq3(mid+1,r);
int L=l,R=mid+1;tot=l-1;
while(L<=mid && R<=r)
{
if(tmp2[L].c<tmp2[R].c)
{
tmp3[++tot]=tmp2[L];
if(!tmp2[L].opt1 && !tmp2[L].opt2)Add(tmp2[L].d,1);
L++;
}
else
{
tmp3[++tot]=tmp2[R];
if(tmp2[R].opt1 && tmp2[R].opt2)ans+=query(tmp2[R].d);
R++;
}
}
while(R<=r)
{
tmp3[++tot]=tmp2[R];
if(tmp2[R].opt1 && tmp2[R].opt2)ans+=query(tmp2[R].d);
R++;
}
for(int i=l;i<L;i++)if(!tmp2[i].opt1 && !tmp2[i].opt2)Add(tmp2[i].d,-1);
while(L<=mid)tmp3[++tot]=tmp2[L++];
for(int i=l;i<=r;i++)tmp2[i]=tmp3[i];
}
代码实现2（cdq+cdq+cdq+cdq)
/*
mail: mleautomaton@foxmail.com
author: MLEAutoMaton
This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
int f=1,sum=0;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
const int N=100010;
struct node
{
int a,b,c,opt1,opt2,opt3,d;
}a[N<<1],tmp1[N],tmp2[N],tmp3[N],tmp4[N];
int n,ans;
void cdq4(int,int);
void cdq3(int,int);
void cdq2(int,int);
void cdq1(int,int);
int main()
{
n=gi();
for(int i=1;i<=n;i++)a[i].a=gi();
for(int i=1;i<=n;i++)a[i].b=gi();
for(int i=1;i<=n;i++)a[i].c=gi();
for(int i=1;i<=n;i++)a[i].d=gi();
cdq1(1,n);
printf("%d
",ans);
return 0;
}
void cdq1(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
cdq1(l,mid);cdq1(mid+1,r);
int tot=l-1;int L=l,R=mid+1;
while(L<=mid && R<=r)
{
if(a[L].a<a[R].a){a[L].opt1=0;tmp1[++tot]=a[L++];}
else{a[R].opt1=1;tmp1[++tot]=a[R++];}
}
while(L<=mid){a[L].opt1=0;tmp1[++tot]=a[L++];}
while(R<=r){a[R].opt1=1;tmp1[++tot]=a[R++];}
for(int i=l;i<=r;i++)a[i]=tmp1[i];
cdq2(l,r);
}
void cdq2(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
cdq2(l,mid);cdq2(mid+1,r);
int tot=l-1;int L=l,R=mid+1;
while(L<=mid && R<=r)
{
if(tmp1[L].b<tmp1[R].b){tmp1[L].opt2=0;tmp2[++tot]=tmp1[L++];}
else{tmp1[R].opt2=1;tmp2[++tot]=tmp1[R++];}
}
while(L<=mid){tmp1[L].opt2=0;tmp2[++tot]=tmp1[L++];}
while(R<=r){tmp1[R].opt2=1;tmp2[++tot]=tmp1[R++];}
for(int i=l;i<=r;i++)tmp1[i]=tmp2[i];
cdq3(l,r);
}
void cdq3(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
cdq3(l,mid);cdq3(mid+1,r);
int tot=l-1;int L=l,R=mid+1;
while(L<=mid && R<=r)
{
if(tmp2[L].c<tmp2[R].c){tmp2[L].opt3=0;tmp3[++tot]=tmp2[L++];}
else{tmp2[R].opt3=1;tmp3[++tot]=tmp2[R++];}
}
while(L<=mid){tmp2[L].opt3=0;tmp3[++tot]=tmp2[L++];}
while(R<=r){tmp2[R].opt3=1;tmp3[++tot]=tmp2[R++];}
for(int i=l;i<=r;i++)tmp2[i]=tmp3[i];
cdq4(l,r);
}
void cdq4(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
cdq4(l,mid);cdq4(mid+1,r);
int tot=l-1;int L=l,R=mid+1,cnt=0;
while(L<=mid && R<=r)
{
if(tmp3[L].d<tmp3[R].d){if((tmp3[L].opt1|tmp3[L].opt2|tmp3[L].opt3)==0)cnt++;tmp4[++tot]=tmp3[L++];}
else{if((tmp3[R].opt1&tmp3[R].opt2&tmp3[R].opt3)==1)ans+=cnt;tmp4[++tot]=tmp3[R++];}
}
while(R<=r){if((tmp3[R].opt1&tmp3[R].opt2&tmp3[R].opt3)==1)ans+=cnt;tmp4[++tot]=tmp3[R++];}
while(L<=mid)tmp4[++tot]=tmp3[L++];
for(int i=l;i<=r;i++)tmp3[i]=tmp4[i];
}