题目描述

给定三个整数数组 A=[A1​,A2​,⋯,A**N​]，B=[B1​,B2​,⋯,B**N​]，C=[C1​,C2​,⋯,C**N​]。

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

1. 1≤i,j,k≤N

2. A**i​<B**j​<C**k​

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1​,A2​,⋯,A**N​。

第三行包含 N 个整数 B1​,B2​,⋯,B**N​。

第四行包含 N 个整数 C1​,C2​,⋯,C**N​。

输出格式

一个整数表示答案。

输入输出样例

输入 #1复制

3
1 1 1
2 2 2
3 3 3

输出 #1复制

27

说明/提示

对于 30% 的数据，1≤N≤100。

对于 60% 的数据，1≤N≤1000。

对于 100% 的数据，1≤N≤105，0≤A**i​,B**i​,C**i​≤105。

#include 
using namespace std;
const int N = 100010; 
int A[N],B[N],C[N];
int cntA[N],cntC[N]; 
int main() {
	int n;
	cin>>n;
	//遍历数组B 其实就是乘法计数原理 看这个位置A有多少个比他小 C有多少个比他大 然后依次相加 
	for(int i=1;i>A[i];
	}
		for(int i=1;i>B[i];
	}
		for(int i=1;i>C[i];
	}
	sort(A+1,A+n+1);
	sort(B+1,B+n+1);
	sort(C+1,C+n+1);//排序 
	for(int i=1,j=1;i<=n;i++)
	{
		while(j<=n&&A[j]<B[i])
		{
			j++;
		}
		cntA[i]=j-1;//查找A的个数 注意要减一 
	}
	for(int i=1,j=1;i<=n;i++)
	{
		while(j<=n&&C[j]<=B[i])
		{
			j++;
		}
		cntC[i]=n-j+1;//查找C的个数 其实跟A差不多 最后把等于的也算上减去就可以了 
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=cntA[i]*cntC[i];
	}
	cout<<ans<<endl;
    return 0;
}