题目描述

给定三个整数数组

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 ≤ 10^5,
0 ≤ Ai,Bi,Ci ≤ 10^5

输入样例

3
1 1 1
2 2 2
3 3 3

输出样例

27

算法1

STL中的二分函数

C++ 代码

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

typedef long long lld;
const int N = 100005;
int a[N], b[N], c[N];
int n;
lld sum;

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

    //由于二分的前提是单调序列 所以预先对a b c排序 直接sort
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    sort(c + 1, c + 1 + n);

    for (int i = 1; i <= n; i++)
    {
        //直接用STL中的两个二分函数解决
        lld x = (lower_bound(a + 1, a + 1 + n, b[i]) - a) - 1;     //在数组a中找比b[i]小的数
        lld y = n - (upper_bound(c + 1, c + 1 + n, b[i]) - c) + 1; //在数组c中找比b[i]大的数
        sum += x * y;
    }

    printf("%lld", sum);
    return 0;
}