排序+二分

#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long 
const int N= 100010;
int n;
int a[N],b[N],c[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(b, b+n);
    sort(c, c+n);

    ll cnt =0 ;
    for(int i=0;i<n;i++){
        int x = b[i];
        ll left,right;

        int l=0,r=n-1;
        while(l<r){ //查找a中最后一个小于b[i]的数
            int mid=(l+r+1)>>1;
            if(a[mid]<x)   l=mid;
            else r =mid-1;
        }

        if(a[l]>=x) left=0;
        else left = l+1;    //注意要加一

        l=0,r=n-1;
        while(l<r){ //查找c中第一个大于b[i]的数
            int mid = l+r>>1;
            if(c[mid]>x)    r= mid;
            else l = mid+1;
        }

        if(c[r]<= x)  right = 0;
        else right = n-l;

        cnt += right*left;
    }
    cout<<cnt;
    return 0;
}

前缀和

#include <iostream>
#include <cstring>
using namespace std;

#define ll long long
const int N = 100010;
int n;
int a[N],b[N],c[N];
int cnt[N],s[N];
int as[N];  //对应下标中有多少个元素小于b[i];
int cs[N];  //对应下标中有多少个元素大于b[i]
ll res;
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]++;

    //求a中有多少个元素小于b[i]
    for(int i=0;i<n;i++)    cnt[a[i]]++;
    for(int i=1;i<N;i++)    s[i] =s[i-1]+cnt[i];
    for(int i=0;i<n;i++)    as[i] = s[b[i]-1];

    memset(cnt,0,sizeof(cnt));
    memset(s,0,sizeof(s));

    //求c中有多少个元素大于b[i]
    for(int i=0;i<n;i++)    cnt[c[i]]++;
    for(int i=1;i<N;i++)    s[i]=s[i-1]+cnt[i];
    for(int i=0;i<n;i++)    cs[i]= s[N-1]-s[b[i]];

    for(int i=0;i<n;i++)    res+=(ll)as[i]*cs[i];   //乘之前先要加上long long，避免超范围

    cout<<res<<endl;

    return 0;

}