递增三元组

题目

给定三个整数数组

A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],

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

1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式
一个整数表示答案。

数据范围

1≤N≤105,
0≤Ai,Bi,Ci≤105

输入样例：

3
1 1 1
2 2 2
3 3 3

输出样例：

27

思路分析

题解

#include<iostream>
#include<cstring>
#include<cstdio>

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]);
        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 = 0; i < n ;i ++){
    
        cnt[a[i]] ++;
    }
    //求cnt的前缀和
    for(int i = 1; i < N;i ++){
    
        s[i] = s[i - 1] + cnt[i];//求cnt的前缀和
    }
    //求as[]
    for(int i = 0 ; i < n ; i++){
    
        as[i] = s[b[i] - 1];
    }
    
    //求cs
    //清空cnt和s
    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];
    }
    //求cs
    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;
}