递增三元组

题目描述

给定三个整数数组

A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],

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

1≤i,j,k≤N
Ai<Bj<Ck

输入格式
第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式
一个整数表示答案。

数据范围
1≤N≤105,
0≤Ai,Bi,Ci≤105

样例

输入

3
1 1 1
2 2 2
3 3 3

输出

27

算法1

(二分查找) $O(nlogn)$

思路：

要求满足Ai<Bj<Ck，先对A[],C[]排序，方便我们查找一个值，我们枚举Bj，
对每个Bj都在A[]里面找小于Bj的值的右边界r，如果不存在这样的值，r = -1；
在C[]里面找大于Bj的值的左边界l，如果不存在这样的值，l = n；
对于每个Bj都有(r + 1) *(n - l)个三元组满足Ai<Bj<Ck。
枚举的Bj的复杂度是O(n),二分查找的复杂度是O(logn),所以时间复杂度是O(nlogn).
要注意结果会爆int。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
typedef long long LL;

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

//二分查找数组a[]小于x的数的右边界
//如果不存在，返回-1
int find_min(int x)
{
    if(a[0] >= x) return -1;
    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = (l + r + 1) / 2;
        if(a[mid] < x) l = mid;
        else r = mid - 1;
    }
    return l;
}

//二分查找数组c[]大于x的数的左边界
//如果不存在，返回n
int find_max(int x)
{
    if(c[n - 1] <= x) return n;
    int l = 0, r = n - 1;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(c[mid] > x) r = mid;
        else l = mid + 1;
    }
    return l;
}

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);


    LL res = 0;

    for(int i = 0; i < n; i++)
    {
        LL n1 = find_min(b[i]), n2 = find_max(b[i]);
        res += (n1 + 1) * (n - n2);
    }

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

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla