F. Yet Another Problem About Pairs Satisfying an Inequality - 题解

比赛与标签

比赛: Codeforces Round 806 (Div. 4) 标签: binary search, data structures, dp, greedy, sortings 难度: *1300

题目大意喵~

主人你好呀~ 这道题是这样的喵：

给你一个长度为 n 的数组 a，我们需要找到有多少对下标 (i, j)，它们需要满足一个非常严格的条件： a[i] < i < a[j] < j。这里的 i 和 j 都是从 1 开始数的哦！

简单来说，就是要我们数一数，有多少个下标对 (i, j)，能同时满足下面四个不等式：

a[i] < i
i < a[j]
a[j] < j
1 <= i, j <= n

输入会包含多个测试用例，我们需要对每个用例都快速地给出答案呐。

解题思路喵~

看到这个题目，最直接的想法就是用两个循环，一个枚举 i，一个枚举 j，然后检查每一对 (i, j) 是不是满足 a[i] < i < a[j] < j。代码大概长这样：

cpp

// 这是一个会超时的暴力想法喵~
long long count = 0;
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (a[i-1] < i && i < a[j-1] && a[j-1] < j) {
            count++;
        }
    }
}

但是喵，题目里的 n 最大有 2 * 10^5 呢！O(n^2) 的复杂度肯定会超时的说。我们必须想个更聪明的办法！

让我们把这个复杂的条件 a[i] < i < a[j] < j 拆开来看。它可以看成是三个小条件的组合：

a[i] < i
a[j] < j
i < a[j]

我们可以换个角度思考：固定 j，然后去数有多少个 i 满足条件。

对于一个固定的 j，如果要让它成为一个合格的配对成员，它自己首先必须满足 a[j] < j。如果这个条件都不满足，那它肯定不能和任何 i 组成我们想要的对子，可以直接跳过啦。

好，假设我们找到了一个满足 a[j] < j 的 j，现在我们需要找有多少个 i 能和它配对。这些 i 需要满足：

a[i] < i （i 本身也得是个“合格”的下标）
i < a[j] （i 的值要小于 a[j] 的值）

如果我们每次都为 j 去遍历一遍所有的 i 来检查，那不又回到 O(n^2) 了嘛？不行不行！

这里的关键在于，对于所有可能的 j，它们对 i 的要求 a[i] < i 都是一样的！我们可以先把所有满足 a[i] < i 的 i 全部找出来，放进一个列表里，我们叫它 good_list 好了。这个列表里的 i 都是“潜在的、合格的” i。

现在，对于一个满足 a[j] < j 的 j，我们只需要在 good_list 中，找到有多少个元素（也就是 i）满足 i < a[j] 就行了。

为了能快速地查找，一个绝妙的办法就是——排序！喵~ 我们可以先把 good_list 从小到大排好序。这样一来，对于每个 j，我们想在 good_list 中找有多少个元素小于 a[j]，就可以用二分查找（Binary Search）啦！

具体来说，我们可以用 lower_bound 函数。lower_bound(good_list.begin(), good_list.end(), a[j]) 会找到 good_list 中第一个大于或等于 a[j] 的元素的位置。那么，在这个位置之前的所有元素，就都是严格小于 a[j] 的啦！这个位置的索引（也就是迭代器减去起始迭代器的结果），就是我们想找的 i 的数量。

所以，我们的完整策略就是：

预处理：遍历一次数组，把所有满足 a[i] < i 的 i (1-based) 收集到 good_list 中。
排序：对 good_list 进行排序。
计数：再次遍历数组，这次是枚举 j。
- 如果当前的 j 满足 a[j] < j，就在排好序的 good_list 中用二分查找，找到有多少个 i 满足 i < a[j]。
- 把这个数量累加到我们的总答案 ans 上。
输出：最后输出 ans 就大功告成啦！

这样一来，预处理是 O(n)，排序是 O(k log k)（k 是 good_list 的大小，最多为 n），计数过程是 O(n log k)。总的时间复杂度就是 O(n log n)，完全可以通过了喵！

代码实现喵~

cpp

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

int main() {
    // 提高cin/cout的效率，这样能跑得更快哦喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // 步骤1：预处理，找出所有满足 a[i] < i 的 "好" 的 i
        // 这里的 i 是 0-based，所以条件是 a[i] < i + 1
        // good_list 存储的是 1-based 的下标
        vector<long long> good_list;
        for (int i = 0; i < n; i++) {
            if (a[i] < i + 1LL) {
                good_list.push_back(i + 1LL);
            }
        }

        // 步骤2：排序，为了后续能用二分查找快速计数
        sort(good_list.begin(), good_list.end());

        // 答案可能会很大，要用 long long 哦
        long long ans = 0;
        
        // 步骤3：遍历所有可能的 j，并对每个合格的 j 计数
        for (int j = 0; j < n; j++) {
            // 检查 j 是否是 "好" 的 j，即 a[j] < j (1-based)
            if (a[j] < j + 1LL) {
                // 如果 j 是合格的，我们就要在 good_list 中找有多少个 i 满足 i < a[j]
                // lower_bound 找到第一个 >= a[j] 的位置
                auto it = lower_bound(good_list.begin(), good_list.end(), a[j]);
                
                // 从开头到 it 的距离，就是 good_list 中 < a[j] 的元素数量
                // 这正是对于当前 j，满足条件的 i 的数量
                ans += (it - good_list.begin());
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

复杂度分析喵~

时间复杂度: O(n log n) 的说
- 第一次遍历数组找到所有“好”的 i，存入 good_list，这需要 O(n) 时间。
- 对 good_list 进行排序，good_list 的大小最多为 n，所以排序需要 O(n log n) 时间。
- 第二次遍历数组枚举 j，对于每个 j，我们使用 lower_bound 在 good_list 中查找，这需要 O(log n) 时间。总共是 n 次，所以这部分是 O(n log n)。
- 总的时间复杂度就是 O(n) + O(n log n) + O(n log n) = O(n log n)，非常高效！
空间复杂度: O(n) 的说
- 我们需要一个 good_list 来存储所有满足条件的 i。在最坏的情况下，所有 n 个下标都满足条件，所以 good_list 的大小会是 n。因此，空间复杂度是 O(n)。

知识点与总结喵~

这道题真是一次有趣的冒险呢！它教会了我们：

转化问题视角：当直接求解困难时，可以试试“固定一端，计数另一端”的思路。这道题里，我们固定 j，然后去高效地统计 i 的数量。
预处理与优化：对于在循环中重复计算的条件（比如 a[i] < i），可以先预处理一遍，把满足条件的结果存起来。这样可以避免大量重复工作。
二分查找的妙用：在排好序的数组中，二分查找不仅仅能找某个元素，还能用来快速统计“有多少元素小于/大于某个值”，这是一个非常强大的技巧！std::lower_bound 和 std::upper_bound 是我们的好朋友喵~
注意细节：
- 题目是1-based索引，而C++数组是0-based，在写代码的时候要小心转换，比如 a[i] < i+1。
- 结果可能会超过32位整数的范围，记得用 long long 来存答案，不然会得到错误的答案哦！

希望这篇题解能帮助到你，喵~ 如果还有不懂的地方，随时可以再来问我哦！一起加油，变得更强吧！

F. Yet Another Problem About Pairs Satisfying an Inequality - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

代码实现喵~ ​

复杂度分析喵~ ​

知识点与总结喵~ ​