AcWing 1236. 递增三元组

AcWing 1236. 递增三元组

给定三个整数数组

$$A=[A1,A2,\dots AN],$$
$$B=[B1,B2,\dots BN],$$
$$C=[C1,C2,\dots 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

看到这个题，我第一次想到的是二分查找，从a中找小于b的下标，从c中找大于b的下标，然后算出总方案数。

代码如下：

#include<iostream>
#include<algorithm>using namespace std;const int N=1e5+10;int a[N],b[N],c[N];int main(void)
{
    int n;long long res=0;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(c,c+n);for(int i=0;i<n;i++){
    int t=b[i];int l1=-1,r1=n-1;while(l1<r1){
    int mid=l1+r1+1>>1;if(a[mid]<t) l1=mid;else r1=mid-1;}int l2=-1,r2=n-1;while(l2<r2){
    int mid=l2+r2+1>>1;if(c[mid]<=t) l2=mid;else r2=mid-1;}l2++;res+=(long long)(l1+1)*(n-l2);}printf("%lld",res);
}

当然也是成功AC，我看到有一些同学有个更简单的做法，我就试试用lower_bound的做法做了一遍。

#include<iostream>
#include<algorithm>using namespace std;const int N=1e5+10;int a[N],b[N],c[N];int main(void)
{
    int n;long long res=0;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(c,c+n);for(int i=0;i<n;i++){
    int t=b[i];int l1=lower_bound(a,a+n,t)-a;int l2=upper_bound(c,c+n,t)-c;res+=(long long)l1*(n-l2);}printf("%lld",res);
}

这个代码比上次要高了一点运行时间。

然后听说y总有更牛逼的一种前缀和的方法，

#include<iostream>
#include<algorithm>using namespace std;const int N=1e5+10;int a[N],b[N],c[N],st[N],cos[N];int main(void)
{
    int n;long long res=0;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];for(int i=0;i<n;i++) st[a[i]]++;for(int i=1;i<N;i++) st[i]+=st[i-1];for(int i=0;i<n;i++) cos[c[i]]++;for(int i=1;i<N;i++) cos[i]+=cos[i-1];for(int i=0;i<n;i++){
    res+=(long long)st[b[i]-1]*(n-cos[b[i]]);// cout<<st[b[i]-1]<<" "<<cos[b[i]]<<endl;}printf("%lld",res);
}

在这里观察到，第一种是前缀和的做法，后两种是二分，还是y总比较牛逼。