Moe's CF Life

Appearance

D. Pashmak and Parmida's problem - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 261 (Div. 2) 标签: data structures, divide and conquer, sortings 难度: *1800

题目大意喵~ ​

主人你好呀~！这道题是说，我们有一个由 n 个整数组成的序列 a。我们先来定义一个函数 f(l, r, x)，它表示在序列的 l 到 r 这个区间里，数字 x 出现了多少次，喵~

我们的任务呢，就是要找出所有满足下面条件的数对 (i, j) 的数量：

  1. 1 ≤ i < j ≤ n
  2. f(1, i, a[i]) > f(j, n, a[j])

简单来说，就是要找有多少个 (i, j) 对，使得 a[i] 在序列开头到位置 i 的出现次数，严格大于 a[j] 在位置 j 到序列结尾的出现次数。是不是很有趣的说？

解题思路喵！ ​

拿到题目，最直接的想法就是暴力枚举所有的 (i, j) 对，然后对每一个数对都去计算 f(1, i, a[i]) 和 f(j, n, a[j])。但是 n 高达 10^6，O(n^2) 的复杂度肯定会让电脑累坏的，会超时的说！所以我们要想一个更聪明的办法，喵~

第一步：简化问题 ​

我们仔细看看这个条件 f(1, i, a[i]) > f(j, n, a[j])。

  • f(1, i, a[i]) 是 a[i] 在前缀 a[1...i] 中的出现次数。
  • f(j, n, a[j]) 是 a[j] 在后缀 a[j...n] 中的出现次数。

这两个值似乎可以预处理出来！我们可以创建两个数组：

  1. pref_count[i]：存储 f(1, i, a[i]) 的值。
  2. suff_count[j]：存储 f(j, n, a[j]) 的值。

怎么计算它们呢？

  • 计算 pref_count: 我们从左到右遍历原数组 a，用一个哈希表（unordered_map）来记录每个数字出现的次数。当遍历到 i 时，我们先将 a[i] 的计数值加一，然后把这个新的计数值存入 pref_count[i]。这样一遍 O(n) 的遍历就可以搞定啦！
  • 计算 suff_count: 同样地，我们从右到左遍历原数组 a，用另一个（或者清空后的）哈希表记录数字出现次数。当遍历到 j 时，同样先将 a[j] 计数值加一，再存入 suff_count[j]。这也是 O(n) 的。

做完这一步，我们的问题就变成了：找出满足 i < j 且 pref_count[i] > suff_count[j] 的数对 (i, j) 的数量。

第二步：高效计数 ​

现在问题简化了，但如果我们还是用两层循环来找这样的数对，不还是 O(n^2) 吗？不行不行，必须祭出我们的神器——树状数组（BIT）！

这个问题可以看作一个二维偏序问题（i < j 是一个维度，pref_count[i] > suff_count[j] 是另一个维度）。处理这类问题的经典思路是：固定一个维度，用数据结构优化另一个维度的查询。

让我们来固定 i，然后去寻找满足条件的 j。如果我们从左到右遍历 i，对于每个 i，我们需要查询所有 j > i 中，有多少个 suff_count[j] 小于 pref_count[i]。这需要在数组的后缀上进行查询，每次查询的范围都不同，处理起来有点麻烦。

逆向思维时间！如果我们从右到左遍历 i 呢？ 我们让 i 从 n-2 遍历到 0（代码实现中的0-based索引）。当我们处理 i 的时候，我们已经处理过了所有比 i 大的索引。 我们可以用一个树状数组，来维护我们已经 "路过" 的 j 的 suff_count[j] 值的频率分布。

具体的算法是这样的喵：

  1. 初始化一个空的树状数组 BIT 和一个总数 total_pairs = 0。树状数组的大小是 n+1，因为 suff_count 的值最大是 n。
  2. 我们从 i = n-2 开始，一直循环到 i = 0。
  3. 在处理当前的 i 之前，我们先把 i+1 这个位置看作一个潜在的 j。我们将它的后缀计数值 suff_count[i+1] 加入到我们的数据结构中。具体操作是 BIT.add(suff_count[i+1], 1)，表示值为 suff_count[i+1] 的后缀计数又多了一个。
  4. 现在，树状数组里存储了所有 j > i 的 suff_count[j] 的频率信息。对于当前的 i，我们需要找有多少个 j 满足 suff_count[j] < pref_count[i]。这不就是查询树状数组中，值域在 [1, pref_count[i] - 1] 区间内的元素个数嘛！
  5. 这个查询操作正是树状数组的拿手好戏！我们用 BIT.query(pref_count[i] - 1) 就能得到这个数量。
  6. 把查询到的结果累加到 total_pairs 中。
  7. 循环结束，total_pairs 就是我们想要的答案啦！

整个过程，预处理是 O(n)，主循环 n 次，每次循环中树状数组的操作是 O(log n)，所以总的时间复杂度是 O(n log n)，完全可以接受！完美解决，喵~

代码实现喵 ​

cpp
#include <iostream>
#include <vector>
#include <unordered_map>

// 树状数组我们用1-based索引，这样写起来最方便喵~
// 计数值的范围是 1 到 n，所以树状数组大小要 n+1
// MAXN 开到 10^6 + 5 更安全一些
const int MAXN = 1000005;
int bit[MAXN];
int n;

// 在树状数组的 idx 位置加上 delta
void add(int idx, int delta) {
    for (; idx <= n; idx += idx & -idx) {
        bit[idx] += delta;
    }
}

// 查询树状数组中 [1, idx] 区间的和
long long query(int idx) {
    long long sum = 0;
    for (; idx > 0; idx -= idx & -idx) {
        sum += bit[idx];
    }
    return sum;
}

int main() {
    // 处理大数据量，加速输入输出是好习惯哦~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 代码里用的是0-based索引，题目描述的1-based i, j 对应代码里的 i-1, j-1

    // 计算 pref_count
    // pref_count[i] 对应题目中的 f(1, i+1, a_i)
    // 也就是 a[i] 在前缀 a[0...i] 中出现的次数
    std::vector<int> pref_count(n);
    std::unordered_map<int, int> freq;
    for (int i = 0; i < n; ++i) {
        pref_count[i] = ++freq[a[i]];
    }

    // 计算 suff_count
    // suff_count[j] 对应题目中的 f(j+1, n, a_j)
    // 也就是 a[j] 在后缀 a[j...n-1] 中出现的次数
    std::vector<int> suff_count(n);
    freq.clear(); // 清空 map，重新使用
    for (int i = n - 1; i >= 0; --i) {
        suff_count[i] = ++freq[a[i]];
    }

    // 我们要统计满足 0 <= i < j < n 且 pref_count[i] > suff_count[j] 的数对 (i, j)
    //
    // 我们从右往左遍历 i (从 n-2 到 0)
    // 对每个 i，我们统计有多少个 j > i 满足 suff_count[j] < pref_count[i]
    // 用树状数组来维护 j > i 的 suff_count[j] 的频率分布
    long long total_pairs = 0;
    
    // 全局/静态数组 bit 默认初始化为0，所以不用手动清零~

    // 循环 i 从 n-2 到 0 (对应1-based的 i 从 n-1 到 1)
    // i = n-1 (0-based) 不需要考虑，因为没有 j > i
    for (int i = n - 2; i >= 0; --i) {
        // 当我们把目光从 i+1 移到 i 时，索引 j = i+1 就变成了一个可用的 j
        // 我们可以把它对应的后缀计数值加入到数据结构中
        add(suff_count[i + 1], 1);
        
        // 现在，树状数组里包含了所有 j > i 的 suff_count[j] 的频率信息
        // 我们查询有多少个 j 满足 suff_count[j] < pref_count[i]
        // 这就是求值在 1 到 pref_count[i] - 1 范围内的频率总和
        // 如果 pref_count[i] 是 1, 查询范围是空的，可以跳过
        if (pref_count[i] > 1) {
            total_pairs += query(pref_count[i] - 1);
        }
    }

    std::cout << total_pairs << std::endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(n log n) 的说。
    • 预处理 pref_count 和 suff_count 使用了 unordered_map，平均每次操作是 O(1)，所以这两步都是 O(n) 的。
    • 主循环遍历 i 从 n-2 到 0，共 n-1 次。在循环内部，add 和 query 操作都是树状数组的标准操作，每次耗时 O(log n)。
    • 所以总的时间复杂度是 O(n) + O(n log n) = O(n log n)。
  • 空间复杂度: O(n) 的说。
    • 输入数组 a，以及我们创建的 pref_count 和 suff_count 数组都需要 O(n) 的空间。
    • 树状数组 bit 也需要 O(n) 的空间。
    • unordered_map 在最坏情况下（所有元素都不同）也需要 O(n) 的空间。
    • 所以总的空间复杂度是 O(n)。

知识点与总结喵~ ​

这道题真是一次愉快的思维体操呢！我们来总结一下学到了什么吧：

  1. 问题转化: 把一个看起来复杂的条件 f(1, i, a[i]) > f(j, n, a[j])，通过预处理转化为更直观的 pref_count[i] > suff_count[j]，是解题的第一步，也是非常关键的一步！
  2. 逆向思维: "从右往左" 的遍历顺序是解决这类计数问题的神来之笔。它巧妙地把对 "未来"（更大下标）的查询，转化为了对 "过去"（已处理过的更大下标）的维护，让问题变得简单。
  3. 树状数组 (BIT): 树状数组是我们的好朋友！它在处理动态单点更新和前缀和查询的问题上效率极高。这道题就是它大显身手的好地方，用来统计满足特定值域范围的元素个数，非常高效，喵~
  4. 二维偏序: 这个问题本质上是一个二维偏序计数问题。通过排序（或按序处理）一个维度，再用数据结构处理另一个维度，是解决这类问题的经典范式。

希望这篇题解能帮助到主人哦！继续努力，享受算法的乐趣吧！喵~ >w<

Released under the MIT License.

Copyright © 2024-present Moe