算法1
(前缀和) $O(n)$
分析
记录3个前缀和数组a[],b[],c[]。
由于元素可能为0,所以提前把每个元素++,再进行个数统计。
设一个maxn作为三个数组的元素最大值。
枚举b中每个元素的个数,乘上a[]中比b小的元素个数乘上c[]中比c小的元素个数。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; //可能会爆int,所以用long long
const int N=1e5+10;
LL a[N],b[N],c[N];
int n,x,maxn=-1;
LL ans;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lld",&x),maxn=max(maxn,x),a[++x]++;
for(int i=0;i<n;i++) scanf("%lld",&x),maxn=max(maxn,x),b[++x]++;
for(int i=0;i<n;i++) scanf("%lld",&x),maxn=max(maxn,x),c[++x]++;
for(int i=1;i<=maxn+1;i++) //求3个数的前缀和
{
a[i]+=a[i-1];
b[i]+=b[i-1];
c[i]+=c[i-1];
}
for(int i=1;i<=maxn+1;i++)
{
ans+=(a[i-1]-a[0])*(b[i]-b[i-1])*(c[maxn+1]-c[i]); //b[i]个数*比b小的a元素总数*比b大的c元素总数
}
cout<<ans<<endl;
return 0;
}
算法2
y总算法 $O(n)$
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int a[N], b[N], c[N];
int as[N]; // as[i]表示在A[]中有多少个数小于b[i]
int cs[N]; // cs[i]表示在C[]中有多少个数大于b[i]
int cnt[N], s[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]), cnt[++a[i]]++;
for (int i = 0; i < n; i ++ ) scanf("%d", &b[i]), b[i] ++ ;
for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]), c[i] ++ ;
// 求as[]
for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i]; // 求cnt[]的前缀和
for (int i = 0; i < n; i ++ ) as[i] = s[b[i] - 1];
// 求cs[]
memset(cnt, 0, sizeof cnt);
memset(s, 0, sizeof s);
for (int i = 0; i < n; i ++ ) cnt[c[i]] ++ ;
for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];
for (int i = 0; i < n; i ++ ) cs[i] = s[N - 1] - s[b[i]];
// 枚举每个b[i]
LL res = 0;
for (int i = 0; i < n; i ++ ) res += (LL)as[i] * cs[i];
cout << res << endl;
return 0;
}