[蓝桥杯 2018 省 B] 递增三元组(两种解法)

[蓝桥杯 2018 省 B] 递增三元组

题目描述

给定三个整数数组 A = [ A 1 , A 2 , ⋯   , A N ] A = [A_1, A_2,\cdots, A_N] A=[A1​,A2​,⋯,AN​]， B = [ B 1 , B 2 , ⋯   , B N ] B = [B_1, B_2,\cdots, B_N] B=[B1​,B2​,⋯,BN​]， C = [ C 1 , C 2 , ⋯   , C N ] C = [C_1, C_2,\cdots,C_N] C=[C1​,C2​,⋯,CN​]。

请你统计有多少个三元组 ( i , j , k ) (i, j, k) (i,j,k) 满足：

1. 1 ≤ i , j , k ≤ N 1 \le i, j, k \le N 1≤i,j,k≤N
2. A i < B j < C k A_i < B_j < C_k Ai​<Bj​<Ck​

输入格式

第一行包含一个整数 N N N。

第二行包含 N N N 个整数 $ A_1, A_2,\cdots, A_N$。

第三行包含 N N N 个整数 $ B_1, B_2,\cdots, B_N$。

第四行包含 N N N 个整数 $ C_1, C_2,\cdots, C_N$。

输出格式

一个整数表示答案

样例 #1

样例输入 #1

3
1 1 1
2 2 2
3 3 3

样例输出 #1

27

提示

对于 30 % 30\% 30% 的数据， 1 ≤ N ≤ 100 1 \le N \le 100 1≤N≤100。

对于 60 % 60\% 60% 的数据， 1 ≤ N ≤ 1000 1 \le N \le 1000 1≤N≤1000。

对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 1 0 5 1 \le N \le 10^5 1≤N≤105， 0 ≤ A i , B i , C i ≤ 1 0 5 0 \le A_i, B_i, C_i \le 10^5 0≤Ai​,Bi​,Ci​≤105。

二分code：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int a[N],b[N],c[N];
int binary_search1(int x){
    int l=0,r=n+1;
    while(l+1<r){
        int mid=(l+r)/2;
        if(a[mid]<x) l=mid;
        else r=mid;
    }
    return l;
}
int binary_search2(int x){
    int l=0,r=n+1;
    while(l+1<r){
        int mid=(l+r)/2;
        if(c[mid]<=x) l=mid;
        else r=mid;
    }
    return r;
}
int main(){
    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);
    sort(b+1,b+1+n);
    sort(c+1,c+1+n);
    long long res=0;
    for(int i=1;i<=n;i++){
        int B=b[i];
        int A=binary_search1(B);
        int C=n-binary_search2(B)+1;
        res+=(long long)A*C;
    }
    cout<<res;
    return 0;
}

双指针code：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int a[N],b[N],c[N];
int main(){
    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);
    sort(b+1,b+1+n);
    sort(c+1,c+1+n);
    long long res=0;
    for(int i=1,j=1,k=1;i<=n;i++){
        int B=b[i];
        while(j<=n&&a[j]<B) j++;
        while(k<=n&&c[k]<=B) k++;
        res+=(long long)(j-1)*(n-k+1);
    }
    cout<<res;
    return 0;
}