Moe's CF Life

Appearance

E. Enemy is weak - 题解 ​

比赛与标签 ​

比赛: Codeforces Beta Round 57 (Div. 2) 标签: data structures, trees 难度: *1900

题目大意喵~ ​

主人，你好呀！这次我们要帮助 Shapur 分析罗马军队的弱点，听起来就好激动呢，喵~

军队的“弱点值”是这样定义的：我们需要找到所有满足 i < j < k 并且对应位置士兵的能力值 a[i] > a[j] > a[k] 的三元组 (i, j, k) 的数量。

简单来说，就是在一个序列 a 中，找到所有“下降三元组”的数量。数组里的每个数字都是独一无二的哦！

输入:

  • 第一行是一个整数 n (3 ≤ n ≤ 10^6)，表示士兵的数量。
  • 第二行是 n 个不同的正整数 a[i] (1 ≤ a[i] ≤ 10^9)，表示每个士兵的能力值。

输出:

  • 一个整数，表示军队的“弱点值”。

解题思路，一起分析吧！ ​

看到这个问题，最直接的想法就是暴力枚举啦！用三层循环，分别枚举 i, j, k，然后检查它们是否满足 i < j < k 和 a[i] > a[j] > a[k]。

cpp
// 暴力思路喵~ (会超时的说！)
long long count = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            if (a[i] > a[j] && a[j] > a[k]) {
                count++;
            }
        }
    }
}

这个方法的时间复杂度是 O(n³)，对于 n 高达 10^6 的数据量，肯定会超时 TLE 的说 T_T。我们必须想一个更聪明的办法！

换个角度看问题 ​

我们要求的 (i, j, k) 满足两个条件：下标递增 i < j < k 和数值递减 a[i] > a[j] > a[k]。 直接找三元组太难了，不如我们固定中间的元素 a[j] 来思考？

对于每一个 a[j]，如果我们能知道：

  1. 在它左边 (下标 i < j) 有多少个数字比 a[j] 大。我们叫这个数量为 left_count[j]。
  2. 在它右边 (下标 k > j) 有多少个数字比 a[j] 小。我们叫这个数量为 right_count[j]。

那么，对于这个固定的 a[j]，它可以构成的“下降三元组”的数量就是 left_count[j] * right_count[j]。因为左边的任何一个大数，和右边的任何一个小-数，都可以和 a[j] 组合成一个满足条件的三元组，喵~

所以，最终的答案就是把所有 j 的贡献加起来： ans = Σ (left_count[j] * right_count[j]) for j from 0 to n-1.

怎样快速计算 left_count 和 right_count 呢？ ​

现在问题就转化成了如何高效地计算这两个数组。如果对每个 j 都再用一个循环去数，那复杂度还是 O(n²)，还是不够快。

这时候，就轮到我们的强大数据结构——树状数组 (Fenwick Tree / BIT) 登场啦！树状数组最擅长解决这种“前缀和”查询和单点更新的问题了。

但是有个小问题：a[i] 的值最大可以到 10^9，我们不能直接开这么大的树状数组。不过，我们只关心数字之间的相对大小关系，不关心它们的具体值。所以，我们可以先进行离散化 (Discretization)，把这些大数映射到从 1 开始的连续整数上。

离散化步骤:

  1. 把原数组 a 复制一份到 temp。
  2. 对 temp 排序并去重。
  3. 对于原数组中的每个 a[i]，用二分查找（lower_bound）在 temp 中找到它的位置，这个位置+1就是它离散化后的新值 comp[i]。

现在，所有值都被映射到了 [1, sz] 这个范围内，sz 是不同数值的个数。我们就可以用树状数组了！

计算 left_count: 我们从左到右遍历原数组（i 从 0 到 n-1）：

  • 对于当前的 a[i] (离散化后为 comp[i])，我们需要知道在 [0, i-1] 这个区间里，有多少个数比 a[i] 大。
  • 我们可以用树状数组来维护已经遍历过的数的出现次数。
  • 到达 i 时，树状数组里已经记录了 a[0] 到 a[i-1] 的信息。
  • 比 a[i] 大的数的数量 = (已经遍历过的数的总数) - (已经遍历过的数中小于等于 a[i] 的数量)。
  • 已经遍历过的数的总数就是 i。
  • 小于等于 a[i] 的数的数量，可以通过查询树状数组的前缀和得到，即 bit.query(comp[i])。
  • 所以 left_count[i] = i - bit.query(comp[i])。
  • 计算完 left_count[i] 后，要把 a[i] 的信息加入树状数组：bit.update(comp[i], 1)。

计算 right_count: 计算 right_count 的方法类似，但这次我们从右到左遍历数组（i 从 n-1 到 0）：

  • 对于当前的 a[i]，我们需要知道在 [i+1, n-1] 这个区间里，有多少个数比 a[i] 小。
  • 我们需要一个新的树状数组。
  • 到达 i 时，这个新的树状数组里记录了 a[i+1] 到 a[n-1] 的信息。
  • 比 a[i] 小的数的数量，就是查询树状数组中小于 comp[i] 的前缀和，即 bit.query(comp[i] - 1)。
  • 所以 right_count[i] = bit.query(comp[i] - 1)。
  • 计算完 right_count[i] 后，把 a[i] 的信息加入这个树状数组：bit.update(comp[i], 1)。

最后，我们有了 left_count 和 right_count 两个数组，把 left_count[i] * right_count[i] 累加起来就是答案啦！这个解法的时间复杂度是 O(n log n)，完全可以通过！

代码实现喵~ ​

cpp
// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll; // 答案可能会很大，用 long long 才保险喵~

// 这是一个树状数组的模板，非常的好用！
struct Fenw {
    int n;
    vector<ll> tree;
    Fenw(int n) : n(n), tree(n+1, 0) {} // 构造函数，初始化大小和数据

    // 单点更新：在 idx 位置增加 delta
    void update(int idx, ll delta) {
        while (idx <= n) {
            tree[idx] += delta;
            idx += idx & -idx; // 这是树状数组的核心魔法！
        }
    }

    // 前缀查询：查询 [1, idx] 的和
    ll query(int idx) {
        ll s = 0;
        while (idx > 0) {
            s += tree[idx];
            idx -= idx & -idx; // 也是核心魔法！
        }
        return s;
    }
};

int main() {
    // 加速输入输出，让程序跑得更快！
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    // --- 离散化部分 ---
    // 把原数组的值复制一份，用来做离散化映射
    vector<ll> temp = a;
    sort(temp.begin(), temp.end()); // 排序
    // 去掉重复的元素，temp 中就只剩下所有不重复的值了
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    int sz = temp.size(); // 离散化后值的范围是 [1, sz]

    // comp 数组存放 a[i] 离散化之后的值
    vector<int> comp(n);
    for (int i = 0; i < n; i++) {
        // lower_bound 找到 a[i] 在排好序的 temp 数组中的位置
        // +1 是因为树状数组的下标通常从 1 开始
        comp[i] = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin() + 1;
    }

    // --- 计算 left_count ---
    Fenw left_tree(sz); // 为计算 left_count 准备一个树状数组
    vector<ll> left_count(n, 0);
    // 从左到右遍历
    for (int i = 0; i < n; i++) {
        // i 是当前位置左边元素的总数
        // left_tree.query(comp[i]) 是左边小于等于 a[i] 的元素数量
        // 两者相减，就是左边大于 a[i] 的元素数量
        left_count[i] = i - left_tree.query(comp[i]);
        // 把当前元素加入树状数组，供后面的元素查询
        left_tree.update(comp[i], 1);
    }

    // --- 计算 right_count ---
    Fenw right_tree(sz); // 为计算 right_count 准备另一个树状数组
    vector<ll> right_count(n, 0);
    // 从右到左遍历
    for (int i = n-1; i >= 0; i--) {
        // right_tree.query(comp[i]-1) 是右边严格小于 a[i] 的元素数量
        right_count[i] = right_tree.query(comp[i]-1);
        // 把当前元素加入树状数组
        right_tree.update(comp[i], 1);
    }

    // --- 计算最终答案 ---
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        // 对于每个 a[i] 作为中间元素，它的贡献是 left_count[i] * right_count[i]
        ans += left_count[i] * right_count[i];
    }
    cout << ans << endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(n log n) 的说。

    • 离散化需要对数组排序，这是 O(n log n)。
    • 计算 left_count 和 right_count 都需要遍历一次数组，每次遍历中会调用树状数组的 query 和 update 操作，单次操作的复杂度是 O(log sz)，其中 sz 是不同元素的数量（sz <= n）。所以这两部分的复杂度都是 O(n log n)。
    • 最后累加答案是 O(n)。
    • 总的来说，瓶颈在于排序和树状数组操作，所以总时间复杂度是 O(n log n)，非常高效！

  • 空间复杂度: O(n) 的说。

    • 我们需要存储原数组 a，离散化用的 temp 数组，映射后的 comp 数组，以及 left_count 和 right_count 数组，这些都是 O(n) 的空间。
    • 两个树状数组的大小都取决于不同元素的数量 sz，所以也是 O(sz) <= O(n) 的空间。
    • 总空间复杂度就是 O(n) 啦。

知识点与总结喵~ ​

这道题真是一道非常经典的题目，完美地展示了如何用高级数据结构优化计数问题，喵~

  1. 核心思想转换: 将一个复杂的三元组计数问题，通过固定中间元的巧妙思路，分解为两个独立的、更简单的计数问题。这个思想在很多组合计数问题中都非常有用！

  2. 树状数组 (Fenwick Tree): 它是解决这类动态前缀和/区间和问题的利器。相比于线段树，树状数组代码更短，常数更小，写起来也更方便快捷。一定要熟练掌握它的 update 和 query 操作哦！

  3. 离散化 (Discretization): 当问题的解只与元素间的相对大小有关，而元素本身的数值范围又很大时，离散化就是不二之选。它可以有效地将值域压缩到一个可控的范围内，从而让我们能够使用像树状数组这样依赖下标的数据结构。

总之，这道题融合了算法思想、数据结构和编程技巧，是一道非常好的练习题。希望这篇题解能帮到主人，要继续加油，变得更强呀！喵~ (ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe