H2. Maximum Crossings (Hard Version) - 题解

比赛与标签

比赛: Codeforces Round 790 (Div. 4) 标签: data structures, divide and conquer, sortings 难度: *1500

题目大意喵~

主人你好呀，这道题是说，我们有上下两排终端，每排都有 n 个线段，从 1 到 n 编号的说。现在要从上面一排的第 i 个线段，连一根电线到下面一排的第 a[i] 个线段。

这些电线都是直的，如果两根电线相交，就产生一个“交叉点”。题目最关键的地方在于，我们可以在线段内部自由选择电线的端点位置。我们的任务就是，通过巧妙地安排这些端点，让交叉点的数量达到最大！

输入会给我们一个整数 n 和一个长度为 n 的数组 a。我们就要算出这个最大的交叉点数量是多少，喵~

解题思路，一起分析吧！

嘿嘿，想要求解最大交叉点，关键就是要弄明白，在什么情况下两根电线才会交叉，以及我们怎么利用“自由选择端点”这个条件，喵~

我们来考虑两根电线，一根是从上方的 i 连到下方的 a[i]，另一根是从上方的 j 连到下方的 a[j]。为了方便讨论，我们假设 i < j 呐。

当 a[i] > a[j] 时：你想想看，i 在 j 的左边，但是 a[i] 却在 a[j] 的右边。这种情况下，不管我们怎么在各自的线段里挪动端点，这两根线都像是打了死结一样，必然会交叉！它们是躲不掉的宿命，喵~
当 a[i] < a[j] 时：这时 i 在 j 的左边，a[i] 也在 a[j] 的左边。我们可以把从 i 出发的线连得靠左一点，从 j 出发的线连得靠右一点，这样它们就可以完美地平行（不完全平行啦，但就是不交叉的意思），互不干扰。既然我们的目标是最大化交叉点，在这种情况下，我们当然选择不让它们交叉，所以贡献是 0。
当 a[i] = a[j] 时：这是最有趣的情况！两根线都连到了下面同一个线段 k = a[i] = a[j]。因为 i < j，所以它们在上方的位置是固定的，一个在左一个在右。在下方的线段 k 上，我们可以自由选择端点位置。如果我们让来自 i 的线的端点在右，来自 j 的线的端点在左，它们就会交叉啦！为了让交叉点最多，我们当然要让它们交叉！

总结一下我们的策略：对于任意一对电线 (i, a[i]) 和 (j, a[j])，只要 i < j，我们就在 a[i] >= a[j] 时让它们交叉。

所以，问题就转化成了一个计数问题：计算有多少对索引 (i, j) 满足 i < j 且 a[i] >= a[j]。

这个问题可以分解成两个子问题，这样会更清晰哦：

情况一：a[i] > a[j] (严格逆序对) 这正是经典的“逆序对”计数问题！
情况二：a[i] = a[j] (相等值对) 计算所有值相等的数对。

对于情况二，我们可以用一个频率数组 freq 来统计每个数字出现的次数。如果一个数字 v 出现了 k 次，那么它们之间可以形成 k * (k - 1) / 2 对 (i, j) 满足 a[i] = a[j]。我们把所有数字的这种情况加起来就好啦，这个用 O(n) 的时间就能搞定。

对于情况一，如果用暴力双重循环来找，时间复杂度是 O(n²)，对于 n 高达 2 * 10^5 的数据肯定会超时的说。这里就需要一个更高效的工具啦，比如**树状数组（Fenwick Tree / BIT）**或者归并排序。树状数组在这里特别好用！

使用树状数组的思路是：我们从左到右遍历数组 a。当我们处理到第 i 个元素 a[i] 时，我们需要知道在它之前（也就是索引 j < i 的位置）有多少个元素 a[j] 满足 a[j] > a[i]。

我们可以用一个树状数组来维护已经遍历过的数字的出现次数。
在处理 a[i] 时，我们先查询树状数组：
- query(n) 可以得到目前已经处理过的元素总数。
- query(a[i]) 可以得到目前已经处理过的元素中，值小于等于 a[i] 的数量。
- 那么 query(n) - query(a[i]) 就是我们想要的——在 a[i] 之前，值大于 a[i] 的元素数量！
把这个数量累加到我们的逆序对计数器里。
查询完之后，不要忘记把当前的 a[i] 也加入到树状数组中，供后面的元素查询使用，即 update(a[i], 1)。

最后，把情况一和情况二的计数结果加起来，就是最终的答案啦！是不是很清晰了呢，喵~

代码实现，看这里喵！

cpp

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 优化一下输入输出速度，让程序跑得飞快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

        // --- Part 1: 计算 a[i] = a[j] 的对数 ---
        // 用一个频率数组统计每个数字出现的次数
        vector<int> freq(n + 1, 0);
        for (int x : a) {
            freq[x]++;
        }

        long long equal_pairs = 0;
        // 对于每个出现次数大于1的数字，计算它能组成的对数
        // 如果一个数出现了 k 次，它可以组成 k*(k-1)/2 对
        for (int i = 1; i <= n; i++) {
            equal_pairs += static_cast<long long>(freq[i]) * (freq[i] - 1) / 2;
        }

        // --- Part 2: 使用树状数组计算严格逆序对 a[i] > a[j] (i < j) ---
        // 树状数组本体
        vector<int> bit(n + 1, 0);
        
        // update操作：在idx位置增加delta
        auto update = [&](int idx, int delta) {
            while (idx <= n) {
                bit[idx] += delta;
                idx += idx & -idx; // 移动到父节点
            }
        };

        // query操作：查询[1, idx]区间的和
        auto query = [&](int idx) {
            int s = 0;
            while (idx > 0) {
                s += bit[idx];
                idx -= idx & -idx; // 移动到下一个区间
            }
            return s;
        };

        long long inversion_count = 0;
        // 从左到右遍历数组
        for (int i = 0; i < n; i++) {
            // query(n) 是已处理的元素总数
            // query(a[i]) 是已处理的元素中 <= a[i] 的数量
            // 两者相减，就是已处理的元素中 > a[i] 的数量
            // 这就是以 a[i] 为较小数的逆序对数量
            inversion_count += query(n) - query(a[i]);
            // 将当前元素 a[i] 加入树状数组，供后续计算
            update(a[i], 1);
        }

        // 总交叉数 = 相等对数 + 严格逆序对数
        cout << inversion_count + equal_pairs << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度: O(N log N) 的说。
- 计算相等值对的部分，我们遍历了一遍数组来构建频率表，然后遍历了一遍频率表，总共是 O(N)。
- 计算严格逆序对的部分，我们遍历了一遍数组，每次遍历都对树状数组进行一次 query 和 update 操作。树状数组的单次操作复杂度是 O(log N)，所以这部分总共是 O(N log N)。
- 两部分加起来，总的时间复杂度由较慢的部分决定，就是 O(N log N) 啦。
空间复杂度: O(N) 的说。
- 我们需要一个 freq 数组来存频率，大小为 O(N)。
- 树状数组 bit 也需要 O(N) 的空间。
- 所以总的空间开销是 O(N)，完全没问题！

知识点与总结喵~

这道题真是一次愉快的思维体操呢！它告诉我们，有时候一个看起来复杂的几何问题，可以通过分析其内在逻辑，转化为我们熟悉的算法问题，喵~

问题转化: 这是解题最核心的一步！将“最大化电线交叉点”这个问题，通过分析交叉条件，转化为了“统计满足 i < j 且 a[i] >= a[j] 的数对数量”。
分治思想: 我们把 a[i] >= a[j] 这个条件拆分成了 a[i] > a[j] 和 a[i] = a[j] 两种情况来分别处理，让思路更清晰，实现也更简单。
树状数组 (BIT): 它是解决动态前缀和、逆序对等问题的超级利器！相比线段树，它代码更短，常数更小，是每一位算法爱好者都应该掌握的可爱数据结构哦！
注意数据范围: 交叉点的数量可能很大，会超过 int 的范围，所以记得要用 long long 来存储结果，不然会因为溢出而得到错误的答案，这可是个常见的陷阱呐！

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

H2. Maximum Crossings (Hard Version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

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

代码实现，看这里喵！ ​

复杂度分析 ​

知识点与总结喵~ ​