递增三元组

要求Ai<Bj<Ck

算法1

(暴力枚举) $O(n^3)$

C++ 代码

/*递增三元组，直接暴力枚举O（n3）10^15超时*/
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=1e5+5;
int a[N],b[N],c[N];

void sc(int *arr,int n){
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
}
int main()
{
    int n;cin>>n;
    sc(a,n);sc(b,n);sc(c,n);
    sort(a+1,a+n+1);sort(b+1,b+1+n);sort(c+1,c+1+n);

    int res=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])
            res++;
    }
    cout<<res<<"\n";

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

/优化枚举，
尝试通过枚举的次序进行优化本题，先枚举B数组，
在A中寻找小于B[i]的数的个数cnt1，
在C中寻找大于B[i]的数的个数cnt2，
带有B[i]的合法选择数就是cnt1cnt2。
用暴力查找时间总的时间复杂度为O(n2)O(n2)，还是会超时。
*/

再查找AC的时候用二分，复杂度就变成了O（nlogn），不超时

C++ 代码

/*递增三元组，二分*/
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=1e5+5;
int a[N],b[N],c[N];

void sc(int *arr,int n){
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
}

int main()
{
    int n;cin>>n;
    sc(a,n);sc(b,n);sc(c,n);
    sort(a+1,a+n+1);sort(c+1,c+1+n);

    long long res=0;
    for(int i=1;i<=n;i++){
        int key=b[i];//枚举b数组的每一个元素
        //lower返回*p是大于等于key的最小值，upper返回*p是大于key的最小值 
        //pos1第一个小于key的数的下标
        //pos2第一个大于key的数的下标 
        int *p1=lower_bound(a+1,a+n+1,key);
        int *p2=upper_bound(c+1,c+n+1,key);
        int pos1=p1-a -1;
        int pos2=p2-c; 
        if(pos1>=1&&pos2<=n)
            res+=(long long)pos1*(n-pos2+1); 
    } 
    cout<<res<<"\n";

    return 0;
}

有坑，res要用longlong， pos1*（n-pos2+1）前面也要加上longlong！！！