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

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1236. 递增三元组 (二分+双指针+前缀和) 原题链接中等

作者：

macat , 2020-08-24 22:37:00 , 所有人可见 , 阅读 12708

145

78

题目分析

首先考虑暴力做法，三个数组嵌套枚举，$O(n^3)$的时间复杂度，$n≤10^5$一定会超时。

尝试通过枚举的次序进行优化本题，先枚举B数组，在A中寻找小于B[i]的数的个数cnt1，在C中寻找大于B[i]的数的个数cnt2，带有B[i]的合法选择数就是cnt1*cnt2。

用暴力查找时间总的时间复杂度为$O(n^2)$，还是会超时。

二分

既然是查找，那么可以考虑进行二分查找，查找前先通过排序预处理三个数组，排序时间复杂度$O(nlog_2n)$,枚举B的所有元素+查找A,C中的元素时间复杂度也是$O(nlog_2n)$，总的时间复杂度降为$O(nlog_2n)$

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

typedef long long LL;
const int N = 1e5+10;
int num[3][N];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < 3; ++i) 
        for(int j = 1; j <= n; ++j) 
            scanf("%d", &num[i][j]);
    for(int i = 0; i < 3; ++i)
        sort(num[i]+1, num[i]+n+1);

    LL ans = 0;
    //枚举B，寻找A满足的个数以及C满足的个数相乘
    for(int i = 1; i <= n; ++i) {
        int key = num[1][i];
        //A中二分查找第一个小于key的数的下标
        int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
        //C中二分查找第一个大于key的数的下标
        int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
        if(pos1 >= 1 && pos2 <= n) {
            ans += (LL)pos1*(n-pos2+1);
        }
    }
    cout<<ans<<endl;
    return 0;
}

双指针

进一步对查找进行优化，对于排过序的数组A和B，寻找A中小于B[i]的元素的个数可以考虑双指针算法，因为每个指针最多移动n次，故查找的时间复杂度降到O(n)，查找C与查找A同理，只是找第一个大于B的位置。
只需要将上述二分程序中的

//二分
for(int i = 1; i <= n; ++i) {
    int key = num[1][i];
    //A中二分查找第一个小于key的数的下标
    int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
    //C中二分查找第一个大于key的数的下标
    int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
    if(pos1 >= 1 && pos2 <= n) {
        ans += (LL)pos1*(n-pos2+1);
    }
}

更改为

//双指针
int a = 1, c = 1;
for(int i = 1; i <= n; ++i) {
    int key = num[1][i];
    while(a<=n && num[0][a] < key) a++;
    while(c<=n && num[2][c] <= key) c++;

    ans += (LL)(a-1)*(n-c+1);
}

完整的双指针程序为：

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

typedef long long LL;
const int N = 1e5+10;
int num[3][N];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < 3; ++i) 
        for(int j = 1; j <= n; ++j) 
            scanf("%d", &num[i][j]);
    for(int i = 0; i < 3; ++i)
        sort(num[i]+1, num[i]+n+1);

    LL ans = 0;
    //枚举B，寻找A满足的个数以及C满足的个数相乘
    int a = 1, c = 1;
    for(int i = 1; i <= n; ++i) {
        int key = num[1][i];
        while(a<=n && num[0][a] < key) a++;
        while(c<=n && num[2][c] <= key) c++;

        ans += (LL)(a-1)*(n-c+1);

    }
    cout<<ans<<endl;
    return 0;
}

前缀和

之前的双指针算法时间复杂度的瓶颈为：排序$O(nlog_2n)$
考虑是否可以不排序在O(n)的时间内解决此问题呢？

既然要排序实现快速的查找A中小于B[i]的数的个数，可以将数组A中所有元素出现的次数存入一个哈希表中，因为数组中元素的范围只有$n^5$, 可以开一个大的数组cnta 作为哈希表。

在枚举B中元素时，我们需要快速查找找小于B[i]的所有元素的总数，只需要在枚举之前先将求出表中各数的前缀和即可。

查找C与查找A同理可得。

C++代码实现

//前缀和
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;
const int N = 1e5+10;
int A[N], B[N], C[N];
int cnta[N], cntc[N], sa[N], sc[N];

int main() {
    int n;
    scanf("%d", &n);
    //获取数i在A中有cntc[i]个，并对cnt求前缀和sa
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &A[i]);
        cnta[++A[i]]++;
    }
    sa[0] = cnta[0];
    for(int i = 1; i < N; ++i) sa[i] = sa[i-1]+cnta[i];
    //B只读取即可
    for(int i = 1; i <= n; ++i) scanf("%d", &B[i]), B[i]++;

    //获取数i在C中有cntc[i]个，并对cnt求前缀和sc
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &C[i]);
        cntc[++C[i]]++;
    }
    sc[0] = cntc[0];
    for(int i = 1; i < N; ++i) sc[i] = sc[i-1]+cntc[i]; 

    //遍历B求解
    LL ans = 0;
    for(int i = 1; i <= n; ++i) {
        int b = B[i];
        ans += (LL)sa[b-1] * (sc[N-1] - sc[b]);
    }
    cout<<ans<<endl;
    return 0;
}

运行时间

二分：725 ms
双指针：454 ms
前缀和：179 ms

76 评论

超级无敌摆烂王 2023-03-28 22:39

一直以为lower_bound是找大于key的第一个位置，upper_bound是找小于key的第一个值，测了半天都有错😭
lower_bound( begin,end,num)：返回第一个大于等于参数key的迭代器减一后变为第一个小于key的位置

upper_bound( begin,end,num)：返回第一个大于参数key的迭代器

一个是大于或等于和一个是大于

正态 11个月前

是滴，其实lower 和 upper 分别对应大于等于、大于还挺形象滴，

15738010079 9个月前

是不是应该是lower_bound( begin,end,num)：…… 减一后变为最后一个小于key的位置？

残夢 8个月前回复了正态的评论

#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int main()
{
int n;
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);
LL res = 0; //答案可能会很大,会爆int

for(int i=0;i<n;i++){
    //此时我们的数字为a【i】
    int key = b[i];
    int l = lower_bound(a,a+n,key) - a - 1;
    int r = upper_bound(c,c+n,key) - c;
    if(l>=-1 && r <n){
        res += (l+1)*(n-r);
    }

    // cout<<"l="<<l<<endl;
    // cout<<"r="<<r<<endl;
    // cout<<"res="<<res<<endl;
    // cout<<" "<<endl;
}


printf("%lld\n", res);
return 0;

}
佬能不能帮我看看为什么答案错误

hxh0014 8个月前回复了 15738010079 的评论

我也感觉是最后一个小于key的位置…

KTpro 2023-03-19 11:11

### 谢谢大佬，orz

Dong_2 9个月前

tql

Flechazo1 9个月前

我的AC不了，能帮看一下吗
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;

const int N=1e5+10;
int a[N],b[N],c[N];
int n;
typedef long long LL;
LL ans=0;

int main()
{
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+1,a+1+n);
sort(b+1,b+1+n);


for(int i=1;i<=n;i++)
{
    //找出a<b
    int l=1,r=n;
    while(l<r)
    {
        int mid=(LL)l+r+1>>1;
        if(a[mid]<b[i]) l=mid;
        else r=mid-1;
    }
    LL temp_a;
    if(a[l]<b[i]) temp_a=l;
    else temp_a=0;

    //找出b>c
    l=1,r=n;
    while(l<r)
    {
        int mid=(LL)l+r>>1;
        if(c[mid]>b[i]) r=mid;
        else l=mid+1;
    }
    LL temp_c;
    if(c[l]>b[i]) temp_c=n-l+1;
    else temp_c=0;

    ans+=temp_a*temp_c;
}
cout<<ans<<endl;
return 0;

}

Flechazo1 9个月前

找到问题了，排序数组那里不小心写错了，本来是打算给c排序的结果把b给排序了

汩潨 10个月前

为什么双指针算法不会超时。如果n个数据，三组，第一层循环n，内层的while循环最坏是2n，那复杂度不也是你n^2吗，难道不会超时吗

Murnomous24 9个月前

排序之后因为元素在不断递增，只会走一轮，也就是O(n)了。

bking 9个月前

因为while中的a,c每一次都不是从1~n循环，而是不断累加

杨睿卿 9个月前

把指针放循环外定义就行了

觊觎貔貅 2023-03-27 13:19

//A中二分查找第一个小于key的数的下标
int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
//C中二分查找第一个大于key的数的下标
int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
为什么找大于不用-1呢？

力_5 10个月前

-num[0]和-num[2]是什么意思啊

s.. 9个月前回复了力_5 的评论

因为数组地址是连续的，这两个函数返回的是一个地址，这个地址减去首地址就是下标了

s.. 9个月前

因为lower_bound()返回的是第一个不小于key的地址，然后我们要的是小于key的个数，所以要减一；upper_bound()返回的是第一个大于key的地址，我们找的也是大于key的，所以不用减一

Pluto_47 1个月前

二分函数蓝桥杯给不给用啊

Bianca 8个月前

大佬爱你，我要扯你裤子

安南_5 8个月前

tql

月下初拥 8个月前

请问为什么统计a中某个数的个数是cnta[A[i]]; 而不是cnta[A[i]]++;

scoutL 8个月前

它不是用的是哈希吗？

熊二爱吃菜花 9个月前

有哪位大佬帮我看一下前缀和为啥过不了最后一个数据，边界问题好难搞
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;

const int N=100010;
int n,a[N],b[N],c[N];
int num[N],s[N];
int as[N],cs[N];
int main(){
cin>>n;
for(int i=1;i<=n;i)cin>>a[i];
for(int j=1;j<=n;j) {cin>>b[j];};
for(int k=1;k<=n;k) cin>>c[k];
//处理as
for(int i=1;i<=n;i) num[a[i]];//记录a[i]出现的次数
for(int i=1;i<=N;i) s[i]=s[i-1]+num[i]; //递推求得关于a[i]的所有前缀和
for(int i=1;i<=n;i) as[i]=s[b[i]-1]; //as代表比b[i]小的数的前缀和
memset(num,0,sizeof num);
memset(s,0,sizeof s);
//处理cs
for(int i=1;i<=n;i) num[c[i]];//记录c[i]出现的次数
for(int i=1;i<=N;i) s[i]=s[i-1]+num[i];//递推求得关于c[i]的所有前缀和
for(int i=1;i<=n;i) cs[i]=s[N-1]-s[b[i]];//cs代表比b[i]大的数的前缀和
//求结果
long long res=0;
for(int i=1;i<=n;i) {
res+=(long long)as[i]*cs[i];
}
cout<<res;
return 0;
}

king_root 9个月前

ans += (LL)sa[b-1] * (sc[N-1] - sc[b]);
大佬，请问这是什么意思？

齐山风 8个月前

因为只要在a数组找小于b[i]的所有数，a数组所有数的出现次数都在cnta里，求个前缀和就意味着，sa[i]代表小于等于i的所有数的出现次数，（数组a下表是有序的嘛）
b[i]又是整数，于是要找小于b[i]的，那不就是sa[b[i]-1]了吗。b[i]是整数
另一个同理，然后乘起来就好。（排列组合）

QCMT 9个月前

为什么求前缀和循环到N而不是n啊，这不会溢出么

沉华 9个月前

n是每个数组的整数个数，而N是最大的数，就比如n = 3时，A[3] = {4,6,9}，由于存储的语句是cnta[A[ i ] ] ；用n作为截止点就不对了，你自己找个数代代就知道了

疾风劲草www 9个月前

orz

Tragedy. 9个月前

orz是什么意思呀

我爱编程666 8个月前回复了 Tragedy. 的评论

膜拜大佬

DxxR 8个月前回复了 Tragedy. 的评论

看起来像一个小人跪着

全岛铁盒 9个月前

#include[HTML_REMOVED]

using namespace std;

const int N = 1e5+10;

typedef long long ll;

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

ll binary_a(int x)
{
int l=0,r=n-1;
while(l[HTML_REMOVED]>1;
if(a[mid]<x)l=mid;
else r=mid-1;
}
return (ll)l;
}

ll binary_c(int x)
{
int l=0,r=n-1;
while(l[HTML_REMOVED]>1;
if(c[mid]>x)r=mid;
else l=mid+1;
}
return (ll)l;
}
int main()
{
cin>>n;

for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
for(int i=0;i<n;i++)cin>>c[i];

sort(a,a+n);
sort(b,b+n);
sort(c,c+n);
ll res=0;

for(int i=0;i<n;i++)
{
    ll l = binary_a(b[i]);//最后一个小于b[i]的数
    //cout<<"l="<<l<<" ";
    ll r = binary_c(b[i]);//第一个大于b[i]的数

    //cout<<"r="<<r<<" ";
    if(a[l]<b[i]&&b[i]<c[r])res+=(l+1)*(n-r);
}
cout<<res;
return 0;

}

飒ksk 9个月前

orz

YMYS 9个月前

orz

pozdno 9个月前

orz

clina 10个月前

orz

糖醋拐杖_8 10个月前

# w我的AC不了有错，能帮忙看下嘛？

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10e5 + 10;
int a[N],b[N],c[N];
int n;
long long res;

int main()
{
    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 + 1,a + n + 1);
    sort(b + 1,b + n + 1);
    sort(c + 1,c + n + 1);

    for (int i = 1; i <= n ; i ++ )
    {
        int x = b[i];

        int l = 1,r = n;
        while (l < r)
        {
            int mid = l + r  + 1>> 1;
            if (a[mid] < x) l = mid;
            else r = mid - 1;
        }
        int x1 = l;
        if (a[l] >= x) x1 = 0;

        l = 1,r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (c[mid] > x) r = mid;
            else l = mid + 1;
        }   
        int x2 = n - l + 1;
        if (c[l] <= x) x2 = 0;
        res += x1 * x2;
     //  cout << x1 <<  " " << x2 << endl;

    }

    cout << res << endl;
    return 0;
}