递增三元组

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

题目描述

给定三个整数数组 \(A = [A_1, A_2,\cdots, A_N]\)，\(B = [B_1, B_2,\cdots, B_N]\)，\(C = [C_1, C_2,\cdots,C_N]\)。

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

1. \(1 \le i, j, k \le N\)
2. \(A_i < B_j < C_k\)

输入格式

第一行包含一个整数 \(N\)。

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

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

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

输出格式

一个整数表示答案

样例 #1

样例输入 #1

3
1 1 1
2 2 2
3 3 3

样例输出 #1

27

提示

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

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

对于 \(100\%\) 的数据，\(1 \le N \le 10^5\)，\(0 \le A_i, B_i, C_i \le 10^5\)。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100000 + 5;
int a[N], b[N], c[N];
int store[N];
int ans = 0;
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);
    int i = 0, j = 0, k = 0;
	while(i < n)
    {
        j = upper_bound(b, b + n, a[i]) - b;
        while(j < n)
        {
            k = upper_bound(c, c + n, b[j]) - c;
            if(k < n)
            {
                ans += n - k;
            }
            j++;
        }
        i++;
    } 
    printf("%d", ans);
	return 0;
}

以上是暴力算法，时间复杂度为\(O(n^2logn)\)最后两个点会超时。仔细探究题目，发现数组A和数组C都与数组B紧密相关，采用双指针优化

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n;
int a[N], b[N], c[N];

signed 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(b, b + n);
    sort(c, c + n);

    LL res = 0, l = 0, r = 0;
    for(int i = 0; i < n; i++)
    {
        while(a[l] < b[i] && l < n) l++;//l停止时，a[l]等于或大于b[i]
        while(c[r] <= b[i] && r < n) r++;//r停止时，c[r]大于b[i]
        res += l * (n - r);
    }

    cout << res << endl;
}

时间复杂度为\(O(nlogn)\), for循环中的语句至多执行n遍