给定三个整数数组

A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],

请你统计有多少个三元组 (i,j,k) 满足：

1≤i,j,k≤N
Ai<Bj<Ck

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式

一个整数表示答案。

数据范围

1≤N≤105,
0≤Ai,Bi,Ci≤105

输入样例：

3
1 1 1
2 2 2
3 3 3

输出样例：

27

C ++代码 1 ------ 整数二分

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 100010;

int a[N], b[N], c[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n;
    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];

    //对数组a,b进行排序-------整数二分的前提条件
    sort(a,a + n);
    sort(c,c + n);

    //left用于返回数组a中第一个小于元素b[i]的那个元素的下标
    //right用于返回数组a中第一个大于元素b[i]的那个元素的下标
    long long ans = 0;
    int left, right;

    for(int i = 0; i < n; i ++){
        int l = 0, r = n - 1;
        while(l < r){
            int mid = r + l + 1 >> 1;
            if(a[mid] < b[i]) l = mid;
            else r = mid - 1;
        }

        //特判，若b[i]比数组a中任意一个数都小的话则返回-1
        if(b[i] <= a[l]) l = -1;
        left = l;

        l = 0, r = n - 1;
        while(l < r){
            int mid = r + l >> 1;
            if(c[mid] > b[i]) r = mid;
            else l = mid + 1;
        }

        //特判，若b[i]比数组a中任意一个数都大的话则返回n
        if(b[i] >= c[r]) r = n;
        right = r;

        //left + 1表示数组a中小于元素b[i]的元素个数，n - 1 -right + 1 即n - right表示数组c中大于元素b[i]的元素个数
        ans += 1ll * (left + 1) * (n - right);
    }

    cout << ans << endl;

    return 0;
}

C++代码 2 ------ 整数二分

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N], b[N], c[N];

int bsearch_l(int l, int r, int i, int &lf){
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(a[mid] < b[i]) l = mid;
        else r = mid - 1;
    }
    if(a[l] >= b[i]) l = -1;
    lf = l;
    return lf;
}

int bsearch_r(int l, int r, int i,int &rt){
    while(l < r){
        int mid = (l + r) >> 1;
        if(c[mid] > b[i]) r = mid;
        else l = mid + 1;
    }
    if(c[l] <= b[i]) l = n;
    rt = l;
    return rt;
}

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];

    //对数组a 和 数组 c进行排序
    sort(a,a + n);
    sort(c,c + n);

    long long ans = 0;
    for(int i = 0; i < n; i ++){
        int lf, rt;
        bsearch_l(0, n - 1, i, lf);
        bsearch_r(0, n - 1, i, rt);
        ans += 1ll * (lf + 1) * (n - rt);
    }

    cout << ans << endl;

    return 0;
}

C ++代码 ------ 前缀和

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N], b[N], c[N];
int cnt[N], s[N];//cnt[i]表示i出现的次数,s[i]表示1 ~ i总共出现的次数
int as[N],cs[N];//分别表示小于b[i],大于b[i]的个数

int main(){
    scanf("%d", &n);

    //因为题干数据范围是从0开始,前缀和下标要从1开始,因此要 ++
    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 = 0; i < N; i ++) s[i] = s[i - 1] + cnt[i];//求cnt[]前缀和
    for(int i = 0; i < n; i ++) as[i] = s[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 ++) s[i] = s[i - 1] + cnt[i];
    for(int i = 0; i < n; i ++) cs[i] = s[N - 1] - s[b[i]];

    long long res = 0;
    for(int i = 0; i < n; i ++) res += 1ll * as[i] * cs[i];

    cout << res << endl;

    return 0;
}