c++递增三元组 排序+二分

解题思路:将 ai<bj<ck 拆成两个式子 bj>ai 和 bj<ck; 所以只需要枚举j即可再用二分找出边界

注意事项:

参考代码:

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N =1e5+10;

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

signed main()

{   

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    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,less<int>());

    sort(b+1,b+1+n,less<int>());

    sort(c+1,c+1+n,less<int>());

    for(int j=1;j<=n;j++){

        //找出 ai<bj bj<ck 枚举b即可

        //找出小于 b[j]的最大下标

        int indexa=lower_bound(a+1,a+n+1,b[j])-a-1;//减1去除等于

        //找出大于b[j]的最小下标

        int indexc=upper_bound(c+1,c+n+1,b[j])-c;

        indexc = n-indexc+1;

        ans+=(indexa*indexc);

    }

    cout<<ans<<endl;

    return 0;

}