n<1e5
数据大小<1e5
使用算法的时间复杂度为 O(n)或者 O(nlogn)

1.暴力求解 O(n3)

代码略

2.二分 O(nlogn)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
typedef long long LL;
int n;
int as[N],cs[N];
int a[N],b[N],c[N];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    for(int i=0;i<n;i++) scanf("%d",&c[i]);
    sort(a,a+n);
    sort(c,c+n);
    int l=0,r=n-1;
    for(int i=0;i<n;i++)
    {
        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(b[i]<=a[0]) as[i]=0;//一定要注意判断边界，否则会WA
        else as[i]=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(b[i]>=c[n-1]) cs[i]=0;//一定要注意判断边界，否则会WA
        else cs[i]=n-l;
    }
    LL res=0;
    for(int i=0;i<n;i++) res+=(LL)as[i]*cs[i];
    cout<<res<<endl;
    return 0;
}

3.前缀和 O(n)

前缀和：用于快速求解某一静态数组的一段区间的和
操作：for() 求数组的前缀和（下标从1开始）
数组下标5-7的的数字的和：a[7] - a[4]

桶排序：
用空间换时间
as[i]:在a数组中小于b[i]的数的个数
cs[i]:在c数组中大于b[i]的数的个数
cnt[i]:表示在a或者c数组中i这个值出现了多少次（桶）
对cnt数组求前缀和，进而通过cnt数组求出as和cs数组的值

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

const int N=100010;

typedef long long LL;

int a[N],b[N],c[N];
int n;
int cnt[N];
int as[N],cs[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) scanf("%d",&a[i]),a[i]++;
    for(int i=0;i<n;i++) scanf("%d",&b[i]),b[i]++;
    for(int i=0;i<n;i++) scanf("%d",&c[i]),c[i]++;

    for(int i=0;i<n;i++) cnt[a[i]]++;
    for(int i=1;i<=N;i++) cnt[i]+=cnt[i-1];
    for(int i=0;i<n;i++) as[i]=cnt[b[i]-1];

    memset(cnt,0,sizeof cnt);
    for(int i=0;i<n;i++) cnt[c[i]]++;
    for(int i=1;i<=N;i++) cnt[i]+=cnt[i-1];
    for(int i=0;i<n;i++) cs[i]=cnt[N-1]-cnt[b[i]];

    LL res=0;
    for(int i=0;i<n;i++)
    {
        res+=(LL)as[i]*cs[i];//as[i]前必须加LL，否则会出错！！
    }

    cout<<res<<endl;
    return 0;
}

4时间差异对比