前缀和

记录a当中每个数出现的次数，记录c当中每个数出现的次数
然后求出这两个数组的前缀和，它的意义就是从0~n中每个数在a/c中出现的次数之和
最后求解只需要将b数组遍历一遍，sum+=a[b[i]-1]*(n-c[b[i]);
最后输出sum
注意要将a，c数组开成long long类型，不然的话求sum的时候两者相乘可能会爆int

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100100;
long long a[N],b[N],c[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int temp;
        scanf("%d ",&temp);
        a[temp]++;
    }
     for(int i=1;i<=n;i++)
    {
        scanf("%d ",&b[i]);
    }
     for(int i=1;i<=n;i++)
    {
        int temp;
        scanf("%d ",&temp);
        c[temp]++;
    }
    for(int i=1;i<=100000;i++)
    {
        a[i]=a[i-1]+a[i];
        c[i]=c[i-1]+c[i];
    }
    long long cnt=0;
    for(int i=1;i<=n;i++)
    {
        cnt+=a[b[i]-1]*(n-c[b[i]]);
    }
    cout<<cnt;
}

用STL中的二分来解决

注意要将x，y开成long long类型，不然的话求sum的时候两者相乘可能会爆int

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],b[N],c[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>c[i];
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    sort(c+1,c+n+1);
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        long long x=lower_bound(a+1,a+n+1,b[i])-a-1;
        long long y=n-(upper_bound(c+1,c+n+1,b[i])-c)+1;
        sum+=x*y;//如果把x和y定义成int类型的话，相乘也会得到int类型的结果
    }
    cout<<sum;
    return 0;
}