三种方法:
1.暴力 $O(n^2)$
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N],b[N],c[N];
int h[N],n;
int main()
{
cin>>n;
for(int i=0;i<n;i++){
}
for(int i=0;i<n;i++) cin>>b[i];
for(int i=0;i<n;i++) cin>>c[i];
LL sum=0;
for(int i=0;i<n;i++){
LL ans1=0,ans2=0;
for(int j=0;j<n;j++){
if(a[j]<b[i]) ans1++;
if(c[j]>b[i]) ans2++;
}
sum+=(LL)ans1*ans2;
}
cout<<sum<<endl;
return 0;
}
2.排序+二分 $O(nlogn)$
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N],b[N],c[N];
int h[N],n;
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
for(int i=0;i<n;i++) cin>>c[i];
sort(a,a+n);
sort(c,c+n);
LL sum=0;
for(int i=0;i<n;i++){
int l=0,r=n-1;
while(l<r){
int mid=l+r+1>>1;
if(a[mid]<b[i]) l=mid;
else r=mid-1;
}
if(a[l]>=b[i]) l=-1;
int ans=l+1;
l=0,r=n-1;
while(l<r){
int mid=l+r>>1;
if(c[mid]>b[i]) r=mid;
else l=mid+1;
}
if(c[l]<=b[i]) r=n;
sum+=(LL)ans*(n-r);
}
cout<<sum<<endl;
return 0;
}
3.哈希+前缀和 $o(n)$
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n;
int a[N],b[N],c[N];
int cnt1[N],cnt2[N];
int s1[N],s2[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i],a[i]++;
for(int i=0;i<n;i++) cin>>b[i],b[i]++;
for(int i=0;i<n;i++) cin>>c[i],c[i]++;
for(int i=0;i<n;i++) cnt1[a[i]]++;
for(int i=1;i<N;i++) s1[i]=s1[i-1]+cnt1[i];
for(int i=0;i<n;i++) cnt2[c[i]]++;
for(int i=N-1;i>=0;i--) s2[i]=s2[i+1]+cnt2[i];
LL sum=0;
for(int i=0;i<n;i++) sum+=(LL)s1[b[i]-1]*s2[b[i]+1];
cout<<sum<<endl;
return 0;
}