时间复杂度O(nlogn)

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N],b[N],c[N];
int lower(int x,int n){
    int l = 0, r = n;
    while(l<r){
        int mid = l + r + 1 >> 1;
        if(a[mid] > x) r = mid - 1;
        else l = mid;
    }
    while(a[l] == x && l > 0) l--;
    return l;
}
int uper(int x,int n){
    int l = 0, r = n;
    while(l<r){
        int mid = l + r >> 1;
        if(c[mid] > x) r = mid;
        else l = mid + 1;
    }
    if(c[l] <= x) return n+1;
    while(c[l] == x && l < n + 1) l++;
    return l;
}
int  main(){
    int n;
    long long res = 0;
    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);
    for(int i = 1; i <= n; i++ ){
        int x = lower(b[i],n); //获得最大小于b[i]的位置
        int y = uper(b[i],n); //获得最小大于b[i]的位置
        res += 1LL * x * (n-y+1);
    }
    cout<<res;
    return 0;
}