题目描述

给定三个整数数组

$A = [A_1, A_2, … A_N]$,
$B = [B_1, B_2, … B_N]$,
$C = [C_1, C_2, … 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, … A_N$。

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

第四行包含 $N$ 个整数 $C_1, C_2, … 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

算法

(暴力枚举) $O(n^2)$

write here…

时间复杂度

write here…

空间复杂度

write here…

C++ 代码

#include <iostream>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll temp,res=0;
ll a[N],b[N],c[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>temp,a[temp]++;
    for(int i=0;i<n;i++)
    cin>>b[i];
    for(int i=0;i<n;i++)
    cin>>temp,c[temp]++;
    //上面是输入
    for(int i=1;i<N;i++)
    a[i]+=a[i-1];
    for(int i=N;i>0;i--)
    c[i]+=c[i+1];
    for(int i=0;i<n;i++)
    res+=a[b[i]-1]*c[b[i]+1];
    cout<<res;
}