算法1

C++ 代码

//二分查找
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=100000+6;
int n,a[N],b[N],c[N];
long long res=0;
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);
    //查找
    for(int i=0;i<n;i++)
    {
        int low_a=0,right_a=n-1;
        while(low_a<right_a)    //找比b[i]小的最后一个数
        {
            int mid=(low_a+right_a+1)>>1;//加1之后改为向上取整(y总二分模版)
            if(a[mid]<b[i])  low_a=mid;
            else  right_a=mid-1;
        }
        if(a[low_a]>=b[i]) low_a=-1;//所有数都大于等于b[i]的时候，low_a=-1,这样最后(low_a+1)*(n-low_b)的时候为0

        int low_b=0,right_b=n-1;
        while(low_b<right_b)   //找比b[i]大的第一个数
        {
            int mid =(low_b+right_b)>>1;
            if(c[mid]>b[i]) right_b=mid;
            else low_b=mid+1;
        }
        if(c[low_b]<=b[i]) low_b=n;//所有数都小于等于b[i]的时候，low_b=n,这样最后(low_a+1)*(n-low_b)的时候为0
        //if(low_a!=0&&low_b!=n-1)//最开始的时候用这种方法判断，后来发现不行
         //如果只有一个数字可以的时候，这种情况无法判断，
         // 例如：
         //  1 4 5
         //  5 5 9
         //  4 6 7（10）  当b[i]=9的时候，c[i]=7和10的时候无法判断
        res+=(long long)(low_a+1)*(n-low_b);

    }
    cout<<res<<endl;

    return 0;
}

算法2

C++ 代码

//前缀和
#include <iostream>
#include <string.h>
using namespace std;
const int N=100005;
int n,a[N],b[N],c[N];
int cnt=0;
int num[N],s[N];
int as[N],cs[N];
int main(){
    cin>>n;//输入
    for(int i=0;i<n;i++) cin>>a[i];//  y总每次要加1，但是我试了一下，从0开始也能过；
    for(int i=0;i<n;i++) cin>>b[i];//  所以大家也别太纠结为什么从1开始了
    for(int i=0;i<n;i++) cin>>c[i];
    //处理as
    for(int i=0;i<n;i++) num[a[i]]++;//  记录a[i]出现的次数

    for(int i=0;i<=N;i++) s[i]=s[i-1]+num[i];// 递推求得关于a[i]的所有前缀和s[i]

    for(int i=0;i<n;i++) as[i]=s[b[i]-1];// as代表比b[i]小的数的前缀和
    //还原数组
    memset(num,0,sizeof(num));
    memset(s,0,sizeof(s));

    //处理cs
    for(int i=0;i<n;i++) num[c[i]]++;//  记录c[i]出现的次数

    for(int i=0;i<=N;i++) s[i]=s[i-1]+num[i];//  递推求得关于c[i]的所有前缀和s[i]

    for(int i=0;i<n;i++) cs[i]=s[N]-s[b[i]];//  cs代表比b[i]大的数的前缀和；
    //注意不能是s[N-b[i]],这样求得的是从0到N-b[i]的前缀和，不是b[i]到N的前缀和

    //求结果
    long long res=0;//  数据量较大，用long long
    for(int i=0;i<n;i++)
    res+=(long long)as[i]*cs[i];//********小学乘法原理，请参考人教版四年级下册数学课本******
    cout<<res<<endl;
    return 0;
}

算法3

C++ 代码

//暴力做法枚举（会超时）
#include <iostream>
using namespace std;
const int N=10000;
int n,a[N],b[N],c[N];
int cnt=0;
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];
    //运算
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    for(int k=0;k<n;k++)
        if(a[i]<b[j]&&b[j]<c[k])
            cnt++;
    cout<<cnt<<endl;
    return 0;
}