方法一:排序+二分

时间复杂度:$O(nlog n)$

思路:

$对于每个B_j，找到A数组中比B_j小的元素个数和C数组中比B_j大的元素个数，$
$相乘即为包含B_j的满足条件的三元组，遍历一遍即可得到所有方案$

代码:

#include<bits/stdc++.h>
using namespace std;

int A[100010],B[100010],C[100010];
int N;
long long int res;  // 防止爆int
// cnt1记录A数组中比Bj小的元素个数
// cnt2记录C数组中比Bj大的元素个数
int cnt1[100010],cnt2[100010];

int main()
{
    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);

    // 二分查找 初始化边界
    A[0] = INT_MIN;
    C[0] = INT_MIN;
    A[N + 1] = INT_MAX;
    C[N + 1] = INT_MAX;

    // 求出A数组中比Bj小的元素个数
    for(int j = 1;j <= N;j++)
    {
        int l1 = 0,r1 = N + 1;
        while(l1 < r1)
        {
            int mid = l1 + r1 + 1 >> 1;
            if(A[mid] >= B[j]) r1 = mid - 1;
            else l1 = mid;
        }
        cnt1[j] = l1;   // 前l1个数均满足A· < Bj
    }

    // 求出C数组中比Bj大的元素个数
    for(int j = 1;j <= N;j++)
    {
        int l2 = 0,r2 = N + 1;
        while(l2 < r2)
        {
            int mid = l2 + r2 >> 1;
            if(C[mid] <= B[j]) l2 = mid + 1;
            else r2 = mid;
        }
        cnt2[j] = N - l2 + 1;   // 后N-l2+1个数均满足C· > Bj
    }
    // 遍历每个Bj 求和所有方案
    for(int i = 1;i <= N;i++)
        res += (long long)cnt1[i]*cnt2[i];  // 防止爆int
    cout << res << endl;
    return 0;
}

方法二:前缀和

时间复杂度:$O(n)$

思路:

$记录A、C数组中每个元素值的出现次数，对于每个B_j，$
$通过前缀和数组即可快速得到A数组中比B_j大和C数组中比B_j小的元素个数$

注意:

$1.前缀和计算时下标会用到-1操作，故下标映射到从1开始(每个元素值+1来实现)$
$初始状态就是0下标，否则初始状态下标为-1会越界$
$2.求前缀和时遍历到n(最大数值上限)而非N(数组元素个数)$
$因为可能当前数组元素个数很少但是数组元素值很大$
$3.空间优化:可以将cnt数组省去，只保留前缀和数组s$

代码:

#include<bits/stdc++.h>
using namespace std;

const int n = 100010;
int A[n],B[n],C[n];
int N;
int as[n];  // as[i]表示在A[]中有多少个数 < B[i]
int cs[n];  // cs[i]表示在C[]中有多少个数 > B[i]
int cnt[n]; // cnt[i]表示在A[]/C[]中元素值i出现的次数
int s[n];   // s[i]表示在A[]/C[]中 元素值0～i出现的总次数
long long int res;  // 存储答案

int main()
{
    cin >> N;
    for(int i = 1;i <= N;i++)
        cin >> A[i],A[i]++;
    for(int i = 1;i <= N;i++)
        cin >> B[i],B[i]++;
    for(int i = 1;i <= N;i++)
        cin >> C[i],C[i]++;

    // 求as[ ]
    for(int i = 1;i <= N;i++) cnt[A[i]]++;
    for(int i = 1;i < n;i++) s[i] = s[i-1] + cnt[i];
    for(int i = 1;i <= N;i++) as[i] = s[B[i] - 1];  // 小于B[i]的数的个数(0~B[i]-1出现的次数)

    // 复原
    memset(cnt,0,sizeof cnt);
    memset(s,0,sizeof s);

    // 求cs[ ]
    for(int i = 1;i <= N;i++) cnt[C[i]]++;
    for(int i = 1;i < n;i++) s[i] = s[i-1] + cnt[i];
    for(int i = 1;i <= N;i++) cs[i] = s[n - 1] - s[B[i]];   // 大于B[i]的数的个数(B[i]+1 ~ 最大元素n出现的次数)

    // 枚举每个B[i]
    for(int i = 1;i <= N;i++)
        res += (long long int)as[i] * cs[i];
    cout << res << endl;

    return 0;
}

// 空间优化版（计数数组充当前缀和数组）
#include<bits/stdc++.h>
using namespace std;

const int n = 100010;
int A[n],B[n],C[n];
int N;
int as[n];  // as[i]表示在A[]中有多少个数 < B[i]
int cs[n];  // cs[i]表示在C[]中有多少个数 > B[i]
int cnt[n]; // 优化后的前缀和数组
long long int res;  // 存储答案

int main()
{
    cin >> N;
    for(int i = 1;i <= N;i++)
        cin >> A[i],A[i]++;
    for(int i = 1;i <= N;i++)
        cin >> B[i],B[i]++;
    for(int i = 1;i <= N;i++)
        cin >> C[i],C[i]++;

    // 求as[ ]
    for(int i = 1;i <= N;i++) cnt[A[i]]++;  // 先充当计数数组
    for(int i = 1;i < n;i++)  cnt[i] += cnt[i-1];   // 计数数组变前缀和数组 优化空间
    for(int i = 1;i <= N;i++) as[i] = cnt[B[i] - 1];  // 小于B[i]的数的个数(0~B[i]-1出现的次数)

    // 复原
    memset(cnt,0,sizeof cnt);

    // 求cs[ ]
    for(int i = 1;i <= N;i++) cnt[C[i]]++;
    for(int i = 1;i < n;i++) cnt[i] += cnt[i-1];
    for(int i = 1;i <= N;i++) cs[i] = cnt[n - 1] - cnt[B[i]];   // 大于B[i]的数的个数(B[i]+1 ~ 最大元素n出现的次数)

    // 枚举每个B[i]
    for(int i = 1;i <= N;i++)
        res += (long long int)as[i] * cs[i];
    cout << res << endl;

    return 0;
}

方法三:杂合

时间复杂度:$O(nlog n)$

思路:

$将A、B、C数组元素均进行排序，对于每个C_k，在B中找到比C_k小的元素的个数$
$对于这些B_j，在A中找到比这些B_j小的元素的个数$
$分别遍历B、C的每一个元素，分别找到A、B中比当前遍历元素要小的元素的个数并存储$
$使用前缀和优化求和时间(O(n)\Rightarrow O(1))、优化存储空间(数值数组充当前缀和数组)$

代码:

#include<bits/stdc++.h>
using namespace std;

int A[100010],B[100010],C[100010];
int N;
// cnt1[j] = i表示A数组中比B[j]小的数共有i项 
// cnt2[k] = j表示B数组中比C[k]小的数共有j项
long long int cnt1[100010],cnt2[100010];/* 优化成前缀和数组进行存储 */

int main()
{
    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);

    // 二分查找 初始化边界
    A[0] = INT_MIN;
    B[0] = INT_MIN;

    for(int j = 1;j <= N;j++)
    {
        int l2 = 0,r2 = N;
        while(l2 < r2)
        {
            int mid = l2 + r2 + 1 >> 1;
            if(A[mid] >= B[j]) r2 = mid - 1;
            else l2 = mid;
        }
        cnt2[j] = cnt2[j-1] + l2;
    }

    for(int k = 1;k <= N;k++)
    {
        int l1 = 0,r1 = N;
        while(l1 < r1)
        {
            int mid = l1 + r1 + 1 >> 1;
            if(B[mid] >= C[k]) r1 = mid - 1;
            else l1 = mid;
        }
        cnt1[k] = cnt1[k-1] + cnt2[l1];
    }
    cout << cnt1[N] << endl;
    return 0;
}