题目描述

给定三个整数数组

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

枚举+二分($O(nlogn)$)

C++ 代码

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

using namespace std;
const int N = 100010;
int a[N],b[N],c[N];

int main()
{
    int n;
    cin >> 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]);
    }
    sort(a + 1,a + n + 1);
    sort(b + 1,b + n + 1);
    sort(c + 1,c + n + 1);
    int res = 0;
    for(int i = 1;i <= n;i++){
        int tar = b[i];
        int l = 1,r = n;
        while(l < r){
            int mid = l + r + 1>> 1;
            if(a[mid] < tar){
                l = mid;
            }else{
                r = mid - 1;
            }
        }

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

        res += less * more;
    }
    cout << res << endl;
    return 0;
}