递增三元组

题目

给定三个整数数组
$$ A = [A_1,A_2, … ,A_N], $$

$$ B = [B_1,B_2, … ,B_N], $$

$$ C = [C_1,C_2, … ,C_N], $$

请你统计有多少个三元组 ( i , j , k ) 满足：
$$ ①、 1 \le i,j,k \le N $$

$$ ②、A_i < B_j < C_k $$

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 $A_1,A_2,…,A_N$。

第三行包含 N 个整数 $B_1,B_2,…,B_N$。

第四行包含 N 个整数 $C_1,C_2,…,C_N$。

输出格式

一个整数表示答案。

数据范围

1 ≤ N ≤ $10^5$,
0 ≤ Ai,Bi,Ci ≤ $10^5$

输入样例：

3
1 1 1
2 2 2
3 3 3

输出样例：

27

题解

解法一：暴力枚举

思路

暴力枚举 i , j , k 符合的情况，然后验证是否符合两点

时间复杂度分析：这样的时间复杂度是O($n^3$)，根据 n 的范围, n 最大为$10^5$ , 那么最坏时间复杂度为 $10^{15}$ , 远远大于 $10^8$

代码：只有部分数据可以通过

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int A[N];
int B[N];
int C[N];

int main()
{
    int n;
    cin>>n;
    for(int i = 1 ; i<=n ; i++) cin>>A[i];
    for(int i = 1 ; i<=n ; i++) cin>>B[i];
    for(int i = 1 ; i<=n ; i++) cin>>C[i];

    int ans = 0;
    for(int i = 1 ; i<=n ; i++)
        for(int j = 1 ; j<=n ; j++)
            for(int k = 1 ; k<=n ; k++)
            {
                if(A[i] < B[j] && B[j] < C[k]) ans++;
            }

    cout<<ans;

    return 0;
}

解法二：前缀和

思路

1、求出 A ，C 中数字的值的个数

2、求出 A , C 的前缀和，利用前缀和求出A , C 的小于等于某个数字的个数，进而求出三元组

ca[ i ] : 表示在 A 中 ， A[i] 这个值出现多少次 , for(int i = 0 ; i<n ; i) ca[ A[i] ] ;

sa : 是ca的前缀和, sa[ i ] = ca[0] + ca[1] + … + ca[i] ; 表示A中小于等于 i 数字个数

注意：这里可以使用前缀和也是因为这里的数据范围比较小，前缀和不会超出才可使用

代码

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
typedef long long LL;

int n;
int A[N],B[N],C[N];
int ca[N],cc[N];//ca表示在 A 中,A[i]这个值出现多少次
int sa[N],sc[N];//sa表示ca的前缀和，sa[i]表示A中小于等于i的数字个数 

int main()
{
    scanf("%d",&n);
    //输入：因为数据中 0≤A[i],B[i],C[i]≤10^5 ，因此加上1,方便求前缀和 
    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]++;



    //求出数量
    for(int i = 0 ; i<n ; i++) ca[A[i]]++;
    for(int i = 0 ; i<n ; i++) cc[C[i]]++;

    //求出前缀和：因为 1≤A[i],B[i],C[i]≤10^5 + 1 ,因此从遍历:1 ~ N 
    for(int i = 1 ; i<N ; i++) sa[i] = ca[i] + sa[i-1];  
    for(int i = 1 ; i<N ; i++) sc[i] = cc[i] + sc[i-1];

    //枚举B 
    LL ans = 0;
    for(int i = 0 ; i<n ; i++)
    {
        LL a = sa[B[i] - 1];//A中小于B[i]的数字
        LL c = n - sc[B[i]];//C中大于B[i]的数字

        ans += a*c;
    }

    cout<<ans;

    return 0;
}

解法三：排序+二分

思路

1、根据从小到大将A、B、C 三个数组进行排序

2、枚举中间的 B 数组的数字

3、二分查找A数组里面最大的小于B[i] 的数字，和C数组里面第一个大于B[i]的数字

4、根据位置就可以得出A数组里面小于B[i] 的数字个数a 和 C数组里面大于B[i] 的数字个数c

5、然后ans += a*c，即可

代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;
typedef long long LL;

int A[N];
int B[N];
int C[N];

//二分寻找第一个小于num的数字的位置
int find(int num , int A[],int n)
{
    int l = 1 , r = n;
    while(l<r)
    {
        int mid = l + r + 1>> 1;
        if(A[mid] < num) l = mid;
        else r = mid - 1;
    }
    return l;
}

//二分寻找第一个大于num的数字的位置
int zhao(int num , int C[],int n)
{
    int l = 1 , r = n;
    while(l<r)
    {
        int mid = l + r >> 1;
        if(C[mid] > num) r = mid ;
        else l = mid + 1;
    }
    return l;
}

int main()
{
    int n;
    cin>>n;
    for(int i = 1 ; i<=n ; i++) cin>>A[i];
    for(int i = 1 ; i<=n ; i++) cin>>B[i];
    for(int i = 1 ; i<=n ; i++) cin>>C[i];

    sort(A ,A+n + 1);//排序
    sort(B ,B+n + 1);
    sort(C ,C+n + 1);

    LL ans = 0;

    for(int i = 1 ; i<=n ; i++)//枚举B数组即可
    {
        int digit = B[i];
        //二分查找A中小于B[i]的数字位置
        LL a = find(digit , A , n);
        LL c = zhao(digit , C , n);

        if(A[a] < digit && digit < C[c]) ans += a*(n + 1 - c);
    }

    cout<<ans;

    return 0;
}