题目分析

样例模拟

算法1:(暴力枚举7/13) $O(n^3)$

略

算法2(排序+二分) $O(n^2*logn)$

通过做题发现：找满足性质左边界判断条件一定是a[mid]>或>= k,右边界是<或<=

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n;
int a[N], b[N], c[N];

int main()
{
    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); // 是从a[0]开始的
    sort(b, b + n);
    sort(c, c + n);

    LL res = 0; // 防止爆int(10^5*10^5 > 1e8)
    for(int i = 0; i < n; i ++ ) // 是对于每一个b[i]来说的
    {
        int l = 0, r = n - 1;
        while(l < r) // 二分找到a数组最后一个小于b[i]的下标
        {
            int mid = l + r + 1 >> 1;
            if(a[mid] < b[i]) l = mid; // 根据题目条件，不能取等
            else r = mid - 1;
        }

        if(a[l] >= b[i]) l --; // 未找到小于b[i]的数,将边界左移
        // 是为了方便后面算res时小于b[i]那部分直接为0，所以对于当前的b[i]就没有满足的res（没找到肯定为0啊）
        int ans_1 = l;

        l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(c[mid] > b[i]) r = mid;
            else l = mid + 1;
        }

        if(c[l] <= b[i]) l ++ ; // 没找到大于的也同理
        int ans_2 = l;
        res += (LL)(ans_1 + 1) * (n - ans_2); // n - l 表示c中大于b[i]的数量
        // 因为都是从0开始的，所以ans_1要加1，而后面公式n-ans_2可以举例子验证
    }

    printf("%lld\n", res);

    return 0;
}