第九届蓝桥杯 B组

//思路:二分 先对三个数组进行sort排序,然后遍历b数组,对于b中的每一个数b[i],在a数组中寻找最后一个
//小于b[i]的数的下标,这里我们记做l.在再c数组中寻找第一个大于b[i]的数的下标,这里我们记做r
//可知a数组中,小于b[i]的数的个数为l+1,c数组中大于b[i]数的个数为n-r.(下标从0开始)
//因此在三元递增组中,以b[i]为中间数的个数为(l+1)*(n-r).
//遍历b数组,res+=(l+1)*(n-r) 即为答案
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)  scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)  scanf("%d", &b[i]);
    for (int i = 0; i < n; i++)  scanf("%d", &c[i]);
    sort(a, a + n);  //二分需要满足单调性
    sort(b, b + n);
    sort(c, c + n);
    LL res = 0;  //答案可能会很大,会爆int
    for (int i = 0; i < n; i++)
    {
        int l = 0, r = n - 1;  //二分查找a数组中最后一个小于b[i]的数的下标
        while (l < r)
        {
            int mid = (l + r + 1) / 2;
            if (a[mid] < b[i])   l = mid;
            else   r = mid - 1;
        }
        if (a[l] >= b[i])   //如果未找到小于b[i]的数,将x标记为-1,后续计算时 x+1==0
        {
            l = -1;
        }
        int x = l;
        l = 0, r = n - 1;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (c[mid] > b[i])   r = mid;
            else  l = mid + 1;
        }
        if (c[l] <= b[i])   //如果未找到大于b[i]的数,将y标记为n,后续计算时 n-y==0;
        {
            r = n;
        }
        int y = r;
        res += (LL)(x + 1)*(n - y);
    }
    printf("%lld\n", res);
    return 0;
}