题目链接

AcWing 1236.递增三元组

引用

z林深时见鹿 AcWing 1236. 递增三元组( 二分解法 )

macat AcWing 1236. 递增三元组 (二分+双指针+前缀和)

冷丁Hacker AcWing 1236. 递增三元组(求赞谢谢兄弟)

田所浩二 AcWing 1236. 递增三元组(模板二分的应用)

小呆呆 AcWing 1236. 递增三元组

题目描述

给定三个整数数组

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

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

$1≤i,j,k≤N$
$A_i<B_j<C_k$

样例

输入格式

第一行包含一个整数 N。

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

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

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

输出格式

一个整数表示答案。

数据范围

$1≤N≤105,$
$0≤A_i,B_i,C_i≤105$

输入样例:

3
1 1 1
2 2 2
3 3 3

输出样例:

27

算法1

(前缀和) $O(n)$

因为我们分别从A,B,C中取出一个数,构成 $A_i < B_j < C_k$ ,如果只是单纯的朴素算法(暴力),那么就是 $O(n^3)$ 的时间复杂度必定超时。那么能不能找出其中的关系呢

其实细心的你肯定发现了 $B_j$ 作为中间数字和其他两位数的关系,我们只要找出A中有多少了数小于当前的B,C中有多少个数大于B,最后相乘累加即可,相乘是因为排列问题

前缀和:当y总说出可以用前缀和方法做的时候我还在疑惑该怎么做,被他这么一讲,好像对于前缀和又有了新的认识,之前只是停留在对于数组的前缀和计算,但是这题用到的不是数组本身的前缀和,而是数组中的数在这个数组里出现次数的前缀和
怎么理解呢?我们计算A、C中数字出现的次数,然后对他们两个求前缀和,接着只要枚举B,算一下A中小于 $B_j$ 的数的个数和C中大于 $C_k$ 的数的个数的乘积,然后累加就行

时间复杂度 $O(n)$

前缀和的时间复杂度是 $O(n)$

C++ 代码

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;

int a[N] , b[N] , c[N];
int as[N] , cs[N];
int cnt[N] , s[N];

int main()
{
    scanf("%d" , &n);

    //因为数据范围是从零开始,计算前缀和时我们习惯下标从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] ++;

    //计算as[]
    for(int i = 0; i < n; i ++) cnt[a[i]] ++;
    for(int i = 1; i < N; i ++) s[i] = s[i - 1] + cnt[i];
    //b[i]- 1是因为b增加了1
    for(int i = 0; i < n; i ++) as[i] = s[b[i] - 1];

    //清空cnt[] 和 s[]
    memset(cnt , 0 , sizeof cnt);
    memset(s , 0 , sizeof s);

    //计算过cs[]
    for(int i = 0; i < n; i ++) cnt[c[i]] ++;
    for(int i = 1; i < N; i ++) s[i] = s[i - 1] + cnt[i];
    //本来b[i]应该减1,但是因为已经加过了,就不需要了,s[N - 1] - s[b[i]] ==> s[r] - s[l - 1]    s[l ~ r] = s[r] - s[l - 1]
    for(int i = 0; i < n; i ++) cs[i] = s[N - 1] - s[b[i]];

    long long res = 0;
    for(int i = 0; i < n; i ++)
        res += (long long)as[i] * cs[i];
    
    printf("%lld" , res);

    return 0;
}

算法2

(sort+二分) $O(nlog_n)$

sort+二分:首先我们先将A、C数组排序,B排不排都无所谓。然后遍历B,二分找出A中小于 $B_j$ 的数的下标,判断一下这个数是不是小于 $B_j$ ,如果不是小于的话就说明A中最小的数都大于它,故小于 $B_j$
的数为零。同理对于C数组也一样,然后将得到的个数相乘再累加即可

时间复杂度 $O(nlog_n)$

sort+二分的时间复杂度是 $O(nlog_n)$

C++ 代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d" , &n);
    
    for(int i = 0; i < n; i ++) scanf("%d" , &a[i]);
    for(int i = 0; i < n; i ++) scanf("%d" , &b[i]);
    for(int i = 0; i < n; i ++) scanf("%d" , &c[i]);
    
    sort(a , a + n) , sort(c , c + n);
    
    long long res = 0;
    for(int i = 0; i < n; i ++)
    {
        int l = 0 , r = n - 1 , mid;
        long long x , y;
        while(l < r)
        {
            mid = l + r + 1 >> 1;
            if(a[mid] < b[i]) l = mid;
            else r = mid - 1;
        }
        if(a[l] < b[i]) x = l + 1;
        else x = 0;
        
        l = 0 , r = n - 1;
        while(l < r)
        {
            mid = l + r >> 1;
            if(c[mid] > b[i]) r = mid;
            else l = mid + 1;
        }
        if(c[l] > b[i]) y = n - l;
        else y = 0;
        
        res += x * y;
    }
    
    printf("%lld" , res);
    
    return 0;
}

算法3

(双指针) $O(nlog_n)$

双指针:首先双指针算法运用的场景必须具备单调性,所以我们同二分一样要先排序,只不过查找的时候用双指针算法,因为查找最多是n次,所以整个算法的时间复杂度是 $O(nlog_n)$,因为双指针是不回溯的,所以它的时间复杂度才会是 $O(n)$。因此我们计算时应该把三个数组都排序一遍,然后用两个变量计数就行了

时间复杂度 $O(nlog_n)$

此时整个算法的时间复杂度是 $O(nlog_n)$ $\Longleftrightarrow$ $O(n + nlog_n)$

C++ 代码


#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

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

int main()
{
    scanf("%d" , &n);

    for(int i = 0; i < n; i ++) scanf("%d" , &a[i]);
    for(int i = 0; i < n; i ++) scanf("%d" , &b[i]);
    for(int i = 0; i < n; i ++) scanf("%d" , &c[i]); 

    sort(a , a + n) , sort(b , b + n) , sort(c , c + n);

    long long res = 0;
    
    //因为指针不能回溯,一旦回溯了时间复杂度就是n三方了,所以将变量定义在循环外
    int j = 0 , k = 0;
    for(int i = 0; i < n; i ++)
    {   
        //指针停下来时一定在不满足条件的那个数上
        while(j < n && a[j] < b[i]) j ++;
        //取等号的原因是因为停下来的时候是不满足大于的,第k个数可能小于也可能等于,这样就会导致可能当前多算了一个,因此指针停下来时一定要在满足条件的那个数上,下一次的时候就能继续了
        while(k < n && c[k] <= b[i]) k ++;
        res += (long long) j * (n - k);
    }

    printf("%lld" , res);
    
    return 0;
}

Q.E.D.


都懂一点,不是很懂的小捞仔