题目描述

关系

内容

给定三个整数数组

$A=[A_1,A_2,\dots A_N]$,
$B=[B_1,B_2,\dots B_N]$,
$C=[C_1,C_2,\dots C_N]$,

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

1. $1\le i,j,k\le N$
2. $A_i<B_j<C_k$

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1,A_2,\dots A_N$。

第三行包含 $N$ 个整数 $B_1,B_2,\dots B_N$。

第四行包含 $N$ 个整数 $C_1,C_2,\dots C_N$。

输出格式

一个整数表示答案。

数据范围

$1\le N\le {10}^5$,
$0\le A_i,B_i,C_i\le {10}^5$

输入样例：

3
1 1 1
2 2 2
3 3 3

输出样例：

27

问题分析

最初思路

先对所有组排序。

对于任意一个 ${\displaystyle a_1}$，我们在数组 B 中二分寻找一个 ${\displaystyle b_m\ge a_1}$，同时再在 C 数组中二分寻找元素 ${\displaystyle c_k\ge b_m\ge a_1}$.

思路分析

所有的枚举的方案都要找一个不重复不遗漏的方案。

然后再想如何进行优化。

先枚举 B 数组。为什么不枚举 A 数组呢？

如果先枚举 A 数组，那么无法应用乘法原理。因为我们在 B 数组和 C 数组中的选择不是独立的（C 数组的选择受限于 B 数组）。所以这种枚举方式是符合要求的。

如果想要时间复杂度符合要求，那么我们只能用一层循环。我们可以先枚举 B 数组，这样 A 数组的选择与 C 数组的选择就是独立的了。

执行流程设计

总结

代码实现

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


typedef long long ll;

const int N = 1e5 + 10;
int n;
int a[N], b[N], c[N];


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(c, c + n);
    
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int t = b[i];
        
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (a[mid] < t) l = mid;
            else r = mid - 1;
        }
        
        ll pa = 0, pc = 0;
        if (a[l] < t) pa = l + 1;
        
        l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (c[mid] > t) r = mid;
            else l = mid + 1;
        }
        
        if (c[l] > t) pc = n - l;
        
        ans += pa * pc;
    }
    cout << ans;
    return 0;
}