题解：P8667 [蓝桥杯 2018 省 B] 递增三元组 (暴力+二分)-EW帮帮网

题解：P8667 [蓝桥杯 2018 省 B] 递增三元组

题目传送门

题目链接

一、题目描述

给定三个整数数组 A、B、C，每个数组包含 N 个元素。要求统计满足 A[i] < B[j] < C[k] 的三元组 (i, j, k) 的数量。

二、题目分析

我们需要找到所有满足 A[i] < B[j] < C[k] 的三元组。直接暴力枚举三个数组的所有组合时间复杂度为 O(N³)，对于 N=1e5 的数据显然不可行。

三、解题思路

排序优化：先对数组 A 和 C 进行排序，这样可以利用二分查找快速统计满足条件的元素数量。
二分查找：对于每个 B[j]，在 A 中找到比它小的元素数量，在 C 中找到比它大的元素数量，然后将这两个数量相乘得到以该 B[j] 为中间值的所有有效三元组数量。
累计求和：将所有 B[j] 对应的有效三元组数量累加，得到最终答案。

四、算法讲解

排序：首先对数组 A 和 C 进行升序排序，以便后续的二分查找操作。
二分查找：
- 对于每个 B[j]，在 A 中使用二分查找找到最后一个小于 B[j] 的元素位置，该位置左边的元素都满足 A[i] < B[j]。
- 在 C 中使用二分查找找到第一个大于 B[j] 的元素位置，该位置右边的元素都满足 C[k] > B[j]。
组合计算：将每个 B[j] 对应的满足条件的 A 元素数量和 C 元素数量相乘，得到以该 B[j] 为中间值的所有有效三元组数量。

五、代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n;
int a[N], b[N], c[N];

// 暴力解法，时间复杂度 O(N³)，只能通过小数据
void solve1()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
            {
                if (a[i] < b[j] && b[j] < c[k])
                    cnt++;
            }
    cout << cnt << "\n";
}

// 自定义二分查找实现
int bifind_a(int x)
{
    int l = -1, r = n + 1;
    while ( l + 1 != r)
    {
        int mid = l + r >> 1;
        if (a[mid] < x)
            l = mid;
        else
            r = mid;
    }
    if (a[l] < x) return l; // 返回小于x的元素个数
    else return 0;
}

int bifind_c(int x)
{
    int l = -1, r = n + 1;
    while (l + 1 != r)
    {
        int mid = l + r >> 1;
        if (c[mid] <= x)
            l = mid;
        else
            r = mid;
    }
    if (c[r] > x)
        return n - r + 1; // 返回大于x的元素个数
    else
        return 0;
}

// 使用自定义二分查找的优化解法
void solve2()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    int cnt = 0;
    sort(a + 1, a + 1 + n);  // 对A数组排序
    sort(c + 1, c + 1 + n);  // 对C数组排序
    for (int i = 1; i <= n; i++)
    {   
        int x = bifind_a(b[i]);  // A中比b[i]小的元素个数
        int y = bifind_c(b[i]);  // C中比b[i]大的元素个数
        cnt += x * y;            // 累加组合数
    }
    cout << cnt << "\n";
}

// 使用STL二分查找函数的优化解法
void solve3()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i];
    int cnt = 0;
    sort(a + 1, a + 1 + n);  // 对A数组排序
    sort(c + 1, c + 1 + n);  // 对C数组排序
    for (int i = 1; i <= n; i++)
    {
        // 使用lower_bound找到第一个不小于b[i]的位置
        int x = lower_bound(a + 1, a + 1 + n, b[i]) - a - 1;
        // 使用upper_bound找到第一个大于b[i]的位置
        int y = n - (upper_bound(c + 1, c + 1 + n, b[i]) - c) + 1;
        cnt += x * y;
    }
    cout << cnt << "\n";
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve2();  // 推荐使用solve2或solve3
    return 0;
}

六、重点细节

数组排序：必须对 A 和 C 数组进行排序才能使用二分查找。
边界处理：在自定义二分查找时，要注意处理所有元素都满足或不满足条件的情况。
索引处理：使用 STL 的 lower_bound 和 upper_bound 时，要注意返回的是迭代器，需要减去数组首地址转换为索引。
数据类型：使用 long long 防止中间结果溢出。

七、复杂度分析

时间复杂度：
- 排序：O(N log N)
- 二分查找：对于每个 B[j] 进行两次二分查找，O(log N)，总共 O(N log N)
- 总时间复杂度：O(N log N)
空间复杂度：O(N)，仅需要存储三个数组。

八、总结

本题通过排序和二分查找将时间复杂度从 O(N³) 优化到 O(N log N)，是典型的利用排序和二分查找优化统计问题的例子。关键在于将三重循环分解为三个独立的一重循环，通过预处理（排序）和快速查询（二分）来大幅提升效率。

题解：P8667 [蓝桥杯 2018 省 B] 递增三元组 (暴力+二分)