蓝桥杯2018年第九届真题-递增三元组 简单二分

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
ll n,a[100005],b[100005],c[100005],bx[100005];
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++)cin>>a[i];
    for(ll i=1;i<=n;i++)cin>>b[i];
    for(ll i=1;i<=n;i++)cin>>c[i];
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    sort(c+1,c+1+n);
    ll t=0;
    for(ll i=1;i<=n;i++){
        ll k1=upper_bound(c+1,c+1+n,b[i])-c;
        k1=n-k1+1;
        bx[i]=k1;
    }
    for(ll i=1;i<=n;i++)bx[i]+=bx[i-1];
    //for(ll i=1;i<=n;i++)cout<<b[i]<<' ';
    //cout<<endl;
    for(ll i=1;i<=n;i++){
        ll k2=upper_bound(b+1,b+1+n,a[i])-b;
        t+=bx[n]-bx[k2-1];
    }
    cout<<t<<endl;
    return 0;
}