题目描述

blablabla

样例

双指针：
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1e6;
int a[N],b[N],c[N];

signed main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++) cin>>c[i];
    sort(c+1,c+1+n);
    for(int i=1,j=1,k=1;i<=n;i++) {
        while(a[j]<b[i]&&j<=n) 
        {
            j++;
        }
        while(c[k]<=b[i]&&k<=n) 
        {
            k++;
        }
        ans+=(j-1)*(n-k+1);
    }
    cout<<ans<<endl;
    return 0;
}

二分加前缀和：
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N=1e6;
int a[N],b[N],c[N],b1[N],c1[N];
int s[N];
int n,ans;

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++) cin>>c[i];
    sort(c+1,c+n+1);
    for(int i=1;i<=n;i++) {
        int l=0,r=n+1;
        while(l+1<r)
        {
            int mid=l+r>>1;
            if(a[mid]<b[i]) l=mid;
            else r=mid;
        }
        b1[i]=l;
    }
    for(int i=1;i<=n;i++) {
        s[i]=s[i-1]+b1[i];
        //cout<<b1[i]<<" ";
    }
    for(int i=1;i<=n;i++) {
        int l=0,r=n+1;
        while(l+1<r)
        {
            int mid=l+r>>1;
            if(b[mid]<c[i]) l=mid;
            else r=mid;
        }
        c1[i]=l;
    }
    for(int i=1;i<=n;i++) {
        ans+=s[c1[i]];
    }
    cout<<ans<<endl;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla