本题首先可以想到用三重for循环来暴力寻找答案,但是会超时,所以我们需要将它优化。
可以从前缀和、二分、双指针这几个角度来看。
前缀和:
我们可以知道,在这三个数组中,我们可以先确定b[]的值,这样a[]和c[]中的值就能得到限制
也就是说,对于每一个b[i],我们只要找到在a[]中小于b[i]的个数,以及在c[]中,大于b[i]的个数,
最后将它们相乘,就能得到答案。
于是我们很容易就能想到用前缀和算法实现。
具体实现看代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N],b[N],c[N];
int cnt[N];
typedef long long LL;
int s[N];//前缀和数组
int ab[N];//用来记录在a数组中对于每一个b[i],小于b[i]的个数
int cb[N];//用来记录在c数组中对于每一个b[i],大于b[i]的个数
int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i++) cin >> a[i],a[i]++;
for(int i = 0;i < n;i++) cin >> b[i],b[i]++;
for(int i = 0;i < n;i++) cin >> c[i],c[i]++;
for(int i = 0;i < n;i++) cnt[a[i]]++;//记录a[i]出现的次数
for(int i = 1;i < N;i++) s[i] = s[i - 1] + cnt[i];
for(int i = 0;i < n;i++) ab[i] = s[b[i] - 1];
memset(cnt,0,sizeof cnt);//一定要记得把这两个数组清零
memset(s,0,sizeof s);
for(int i = 0;i < n;i++) cnt[c[i]]++;//记录c[i]出现的次数
for(int i = 1;i < N;i++) s[i] = s[i - 1] + cnt[i];
for(int i = 0;i < n;i++) cb[i] = s[N - 1] - s[b[i]];
LL res = 0;//有可能会爆int
for(int i = 0;i < n;i++) res += (LL)ab[i] * cb[i];
cout << res <<endl;
return 0;
}