Moe's CF Life

Appearance

F. MEX vs MED - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 828 (Div. 3) 标签: math, two pointers 难度: *2000

题目大意喵~ ​

喵~ 主人 sama，下午好呀！今天我们来攻略一道非常有趣的题目哦！(ฅ'ω'ฅ)

题目会给我们一个长度为 n 的排列 p，里面包含了从 0 到 n-1 的所有数字，每个数字只出现一次。我们的任务是，找出这个排列中有多少个连续的子区间 [l, r]，满足一个奇妙的条件：这个子区间的 mex 值要大于它的 med 值。

让本猫娘来解释一下这两个概念吧：

  • MEX (Minimum Excluded value): 对于一个数字集合 S，它的 mex 是指不在 S 中出现的最小非负整数。比如说，mex({0, 1, 3, 4}) 就是 2，因为 0 和 1 都在，但 2 不在。
  • MED (Median): 对于一个数字集合 S，它的 med 就是中位数。先把 S 里的数字从小到大排个序，如果集合大小是 k，那么中位数就是排在第 floor((k+1)/2) 位置的那个数。比如 med({0, 4, 1, 3})，排序后是 {0, 1, 3, 4}，长度是 4，中位数在第 floor((4+1)/2) = 2 个位置，所以是 1。

所以，我们的目标就是数一数，有多少个子区间能满足 mex > med 这个条件！

解题思路大揭秘！ ​

直接去枚举所有 O(n^2) 个子区间，再对每个子区间都花时间计算 mex 和 med，那肯定会超时超到天上去的啦！(>ω<) 我们需要一种更聪明的办法，喵~

第一步：把条件变个身！ ​

mex(S) > med(S) 这个条件看起来好抽象呀，我们来把它变得更具体一点！

假设我们有一个子区间 S，它的长度是 k。

  • 设 m = mex(S)。根据 mex 的定义，这意味着数字 {0, 1, ..., m-1} 一定都 在集合 S 里面。这是最关键的突破口哦！
  • 设 v_med = med(S)。
  • 我们的条件是 m > v_med。

现在我们来思考 med。v_med 是 S 排序后第 floor((k+1)/2) 个元素。如果 v_med 要比 m 小，这意味着什么呢？这意味着 S 中至少有 floor((k+1)/2) 个元素的值是小于 m 的。

那么，S 中有哪些元素是小于 m 的呢？不就是我们刚才说的集合 {0, 1, ..., m-1} 嘛！这些元素的数量正好是 m 个。

所以，" S 中至少有 floor((k+1)/2) 个元素的值小于 m " 这个条件，就变成了 m >= floor((k+1)/2)。

喵呀！你看，复杂的不等式一下子就变得清晰可爱了呢！ mex(S) > med(S) 等价于 m >= floor((|S|+1)/2)

第二步：重新定义我们的任务 ​

现在问题就变成了： 对于一个长度为 k 的子区间 S，我们要计算有多少个满足 mex(S) >= floor((k+1)/2)。

我们再深入一点。设 m_req = floor((k+1)/2)。 条件 mex(S) >= m_req 等价于：集合 S 必须包含所有从 0 到 m_req - 1 的整数，也就是 {0, 1, ..., m_req - 1}。

是不是感觉胜利在望了呀？我们的最终任务是： 对每个长度 k (从 1 到 n)，统计有多少个长度为 k 的子区间，它包含了集合 {0, 1, ..., floor((k+1)/2) - 1}。

第三步：如何高效地计数呢？ ​

我们可以遍历所有可能的子区间长度 k，从 1 到 n。

对于一个固定的 k，我们需要找到包含 {0, 1, ..., m_req - 1} 的子区间数量，其中 m_req = floor((k+1)/2)。 为了方便，我们先预处理一下，用一个 pos 数组记录下每个数字 x 在原排列 p 中的位置，即 pos[x] = i。

一个子区间 p[l...r] 要包含 {0, ..., v} (这里 v = m_req - 1)，它的左右端点必须满足：

  1. l <= min(pos[0], pos[1], ..., pos[v])
  2. r >= max(pos[0], pos[1], ..., pos[v])

我们设 L_v = min(pos[0], ..., pos[v])，R_v = max(pos[0], ..., pos[v])。 所以，合法的 l 和 r 必须满足 l <= L_v 并且 r >= R_v。

同时，我们还知道子区间的长度是 k，所以 r - l + 1 = k，也就是 r = l + k - 1。 把 r 代入 r >= R_v，得到 l + k - 1 >= R_v，即 l >= R_v - k + 1。

最后，l 作为一个长度为 k 的子区间的起始点，它自己也必须在 [0, n-k] 的范围内。

把所有条件合在一起，l 的取值范围就是： max(0, R_v - k + 1) <= l <= min(n - k, L_v)

对于每个 k，我们只要计算出 L_v 和 R_v，就能算出满足条件的 l 有多少个啦！

第四步：双指针思想，加速！ ​

如果对每个 k 都重新计算 L_v 和 R_v，还是有点慢。 我们观察到，当 k 从 1 增加到 n 时，m_req = floor((k+1)/2) 是单调不减的。它只在 k 从偶数变为奇数时才会增加 1。

这启发我们可以用一个类似双指针/滑动窗口的方法来优化！ 我们用一个循环遍历 k from 1 to n。在循环中，我们维护当前的 L 和 R，它们是当前 m_req 所需数字集合的最小和最大位置。 当 k 增加导致 m_req 变大时，我们只需要把新加入的那个数字的位置（比如 pos[m_req - 1]）更新到 L 和 R 中即可。

就像猫咪追着激光笔一样，我们的 L 和 R 也轻快地更新着范围，每次循环都用 O(1) 的时间计算出当前 k 的答案，总时间复杂度就是 O(n) 啦！喵~

代码实现喵！ ​

cpp
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> p(n);
    std::vector<int> pos(n);
    // 先用 pos 数组记录下每个数字 p[i] 到底藏在哪个位置 i，方便我们快速查找~
    for (int i = 0; i < n; ++i) {
        std::cin >> p[i];
        pos[p[i]] = i;
    }

    if (n == 1) {
        std::cout << 1 << "\n";
        return;
    }

    long long ans = 0;
    
    // L 和 R 分别是当前需要包含的数字集合 {0, 1, ..., current_m_val-1} 所在的最左和最右位置
    // 一开始，k=1时，m_req=1，需要包含{0}，所以 L 和 R 都是 0 的位置
    int L = pos[0];
    int R = pos[0];
    // current_m_val 记录了我们当前处理的 m_req 值
    int current_m_val = 1;

    // 我们开始枚举子区间的长度 k，从 1 到 n 呐~
    for (int k = 1; k <= n; ++k) {
        // 根据我们神奇的推导，计算出当前长度 k 至少需要的 mex 值
        int m_req = (k + 1) / 2;
        
        // 如果 k 变大，导致我们需要的数字变多了 (m_req 增加了)
        if (m_req > current_m_val) {
            // 那么就要把新的数字 (也就是旧的 m_req 值，即 current_m_val) 的位置也考虑进来
            // 更新 L 和 R 的范围，把新伙伴的位置也加入到我们的大家庭里来！
            L = std::min(L, pos[current_m_val]);
            R = std::max(R, pos[current_m_val]);
            current_m_val = m_req;
        }

        // v = m_req - 1，我们需要包含 {0, ..., v}
        // R 是 max(pos[0]...pos[v]), L 是 min(pos[0]...pos[v])
        // 子区间 [l, r] 长度为 k, r=l+k-1
        // 约束条件: l <= L, r >= R => l+k-1 >= R => l >= R-k+1
        // l 的范围: [0, n-k]
        // 综合起来，l 的合法范围是 [max(0, R-k+1), min(n-k, L)]
        
        long long min_l = std::max(0, R - k + 1);
        long long max_l = std::min(n - k, L);

        // 如果 max_l >= min_l，说明存在合法的左端点 l
        if (max_l >= min_l) {
            // 这就是我们推导出的魔法公式，计算合法的左端点 l 有多少个~
            ans += (max_l - min_l + 1);
        }
    }
    
    std::cout << ans << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析 🐾 ​

  • 时间复杂度: O(n) 的说。我们只需要预处理 pos 数组花 O(n) 时间，然后主循环从 1 遍历到 n，循环体内的所有操作都是 O(1) 的常数时间。所以每个测试用例的总时间复杂度是 O(n)！超级快！
  • 空间复杂度: O(n) 的说。我们需要一个 p 数组和一个 pos 数组来存放排列和位置信息，所以空间复杂度是 O(n) 喵~

知识点与总结 ​

这道题真是一道美味的小鱼干，回味无穷呐！

  1. 核心思想 - 问题转化: 这道题最最关键的一步，就是把 mex > med 这个看起来很头疼的条件，通过分析 mex 和 med 的定义，一步步转化为 mex >= floor((k+1)/2)，最终变成对子区间必须包含 {0, ..., m_req - 1} 的要求。这种化繁为简的观察和推导能力，在算法竞赛中非常重要哦！

  2. 算法技巧 - 迭代与优化: 我们通过枚举子区间长度 k，并将问题转化为对 k 的计数问题。然后利用 m_req 的单调性，使用了类似双指针的思想，动态地维护 L 和 R 的范围，避免了重复计算，将复杂度从 O(n^2) 优化到了 O(n)。

  3. 注意事项: 在计算合法 l 的数量时，一定要注意边界！l 的下界要和 0 取 max，上界要和 n-k 取 min。最后计算数量时，如果上界小于下界，结果是 0 而不是负数。这些小细节是AC的关键哦！

希望本猫娘的讲解对主人 sama 有帮助！多做这样的题，可以锻炼我们的观察力和数学推导能力！主人 sama 一定可以变得更强的！加油喵~ ( ´ ▽ ` )ﾉ

Released under the MIT License.

Copyright © 2024-present Moe