枚举+前缀和巧用

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N=100100;

int a[N], b[N], c[N];

int n;

int cnt[N], s[N];  //s[i]存小于等于i的数的数目
int num1[N], num2[N];
long long res;

int main()
{
    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]);

    //使用前缀和来计算比b[i]小的数目
    //a[i]

    for(int i=1; i<=n; i++) cnt[a[i]]++;

    s[0] = cnt[0];
    for(int i=1; i<N; i++) s[i] = s[i-1] + cnt[i] ;
    for(int i=1; i<=n; i++) num1[i] = s[b[i]-1] ;

    memset(cnt, 0, sizeof(cnt));
    memset(s, 0, sizeof(s));

    //计算c[i]中比b[i]大的数目

    for(int i=1; i<=n; i++) cnt[c[i]]++;
    s[0] = cnt[0];
    for(int i=1; i<=N; i++) s[i] = s[i-1] + cnt[i] ;
    for(int i=1; i<=n; i++) num2[i] = s[N] - s[b[i]] ;

    for(int i=1; i<=n; i++) res+= (long long)num1[i] *num2[i];

    cout<<res;

    return 0;

}