算法1 (sort+二分) $O(nlogn)$

分析as数组的意义

as[i]数组的意思是，在a数组中，有多少个数字比b[i]（i下标相同）小
所以，根据乘法原理，三元组的数目等于对应于每一个i，as[i]和cs[i]相乘

如何得到as数组

以a数组为例子：
二分的目的就是为了找到a数组中有多少个数比b[i]小
类似于 123456 中有多少个数字比4小
很明显，比4小的有123
我们就可以通过返回数组元素为4的数组下标，来获得一共有多少个数小于4
4的数组下标是3，所以，由于单调性，前面比它小的数字有3个

C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 100010;
typedef long long ll;
int n;
int a[maxn];
int b[maxn];
int c[maxn];
int as[maxn];
int cs[maxn];


int find(int b, int l, int r, bool flag)  
{
    if (flag == 1)
    {
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (a[mid] < b)
                l = mid;
            else
                r = mid - 1;
        }
        if (a[l] >= b)
            return -1; // 应该返回-1，因为后面会index++
        else
            return l;
    }
    else
    {
        while (l < r)
        {
            int mid = l + r >> 1;
            if (c[mid] > b)
                r = mid;
            else
                l = mid + 1;
        }
        if (c[r] <= b)
            return n; // 这里要用n
        else
            return r;
    }
}


int main()
{
    cin >> 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(c, c + n);

    // 获取a数组中有多少个比b[i]小的数字
    ll index;
    for (int i = 0; i < n; i++)
    {
        index = find(b[i], 0, n - 1, 1);
        index++;
        as[i] += index;  // index - 0 +1 == index++
    }
    for (int i = 0; i < n; i++)
    {
        index = find(b[i], 0, n - 1, 0);
        index = n - index;  // (n-1) - index +1
        cs[i] += index;
    }

    ll res = 0;
    for (int i = 0; i < n; i++)
    {
        res += (ll)as[i] * cs[i];
    }
    cout << res << endl;
    return 0;
}