D. Swap Dilemma - 题解

比赛与标签

比赛: Codeforces Round 956 (Div. 2) and ByteRace 2024 标签: constructive algorithms, data structures, divide and conquer, greedy, math, sortings 难度: *1700

题目大意喵~

你好呀，指挥官！这道题是这样的喵~

我们有两个长度为 n 的数组 a 和 b，里面的数字都是独一无二的正整数哦。我们有一种特殊的操作：

1. 在数组 a 中选择两个下标 l 和 r (l <= r)，然后交换 a[l] 和 a[r]。
2. 同时，在数组 b 中也选择两个下标 p 和 q (p <= q)，然后交换 b[p] 和 b[q]。
3. 这个操作有一个限制条件，就是 r - l 必须等于 q - p。也就是说，在 a 和 b 中交换的两个元素之间的距离必须是相等的！

我们的目标是，通过任意多次这样的操作，能不能让数组 a 和数组 b 变得完全一样呢？（也就是对于所有 i，都有 a[i] == b[i]）

如果可以，就输出 "YES"，不然就输出 "NO"，很简单对吧~？

解题思路大揭秘！

这道题看起来有点复杂，但只要我们抓住核心，就能把它变简单哦，喵~

第一步：基础检查

首先，一个最最基本的想法是：如果 a 和 b 最终能变得一样，那么它们包含的元素集合必须是完全相同的！就像是两袋不同颜色的猫粮，如果颜色种类和数量都对不上，那怎么重新排列都变不成一样的嘛。

所以，我们可以先把 a 和 b 分别排序，然后比较一下。如果排序后的两个数组不相等，那说明它们的元素集合根本就不同，直接输出 "NO" 就好啦！这是一个非常重要的预处理步骤哦。

第二步：问题的转化

好，现在我们知道 a 和 b 包含的元素是一样的了。这意味着 a 是 b 的一个排列。我们的目标就是通过操作把 a 和 b 变成同一个数组。

为了更清晰地研究排列关系，我们可以把具体的数值“忘掉”，只关心它们的位置。我们可以把两个数组里的所有数，按照从小到大的顺序，映射成 0, 1, 2, ..., n-1。

举个栗子：如果 a 和 b 排序后都是 {10, 20, 50, 80}，那么我们就建立一个映射：10 -> 0, 20 -> 1, 50 -> 2, 80 -> 3。 然后用这些新的“排名”来代替原来的数值，得到两个新的排列数组 a_perm 和 b_perm。这样一来，问题就变成了：我们能否通过操作，让 a_perm 和 b_perm 变成同一个排列（比如都变成 0, 1, ..., n-1）？

第三步：核心不变量——逆序对的奇偶性

现在让我们来分析一下那个奇特的交换操作。 一次操作 = swap(a[l], a[r]) + swap(b[p], b[q])。

在排列理论中，有一个非常重要的概念叫做逆序对。一个排列的逆序对数量的奇偶性，被称为这个排列的奇偶性。一个非常关键的性质是：对一个排列进行一次交换，其逆序对数量的奇偶性会发生改变。也就是说，奇数会变偶数，偶数会变奇数。

回到我们的操作：

• swap(a[l], a[r]) 会让 a_perm 的逆序对数量的奇偶性改变。
• swap(b[p], b[q]) 会让 b_perm 的逆序对数量的奇偶性改变。

每次操作，我们都同时改变了 a_perm 和 b_perm 的奇偶性。这意味着，a_perm 的逆序对奇偶性 和 b_perm 的逆序对奇偶性，要么同时保持不变（奇->偶，奇->偶），要么同时改变（偶->奇，偶->奇）。

所以，inv(a_perm) % 2 和 inv(b_perm) % 2 之间的关系是恒定的！ 如果一开始它们的奇偶性就相同，那么无论我们做多少次操作，它们的奇偶性都会保持相同。 如果一开始它们的奇偶性就不同，那么它们永远也变不成相同的。

我们的目标是让 a 和 b 变得完全一样。假设我们成功地把它们都变成了某个目标数组 c。那么 a_perm 和 b_perm 也会变成同一个目标排列 c_perm。此时，它们的逆序对数量肯定是相同的，奇偶性也必然相同。

因此，我们可以得出一个结论：只有当初始的 a_perm 和 b_perm 的逆序对数量奇偶性相同时，才有可能让它们最终变得相同。

因为题目给的操作非常灵活（只要距离相等就行），我们可以认为只要奇偶性满足条件，就总能找到方法完成转换。所以这个条件既是必要条件，也是充分条件！

第四步：如何计算逆序对？

计算一个排列的逆序对数量，一个经典高效的方法是使用**树状数组（Fenwick Tree）**或者归并排序。这里的AC代码就用到了树状数组，喵~

使用树状数组计算逆序对的步骤是：

1. 准备一个和排列长度一样大的树状数组，全部初始化为0。
2. 从后往前（或者从前往后）遍历排列 p。
3. 对于当前元素 p[i]，我们用树状数组查询在它之前（或者之后，取决于遍历顺序）已经处理过的、且比 p[i] 小的数的个数。
4. 将查询结果累加到总逆序对数量中。
5. 在树状数组中将 p[i] 对应位置的值加1，表示我们处理过这个数了。

例如，从后往前遍历：对于 p[i]，我们查询 query(p[i] - 1)，得到的是在 i 右边且比 p[i] 小的数的个数，这正是以 p[i] 为较大数的逆序对的数量。

总结一下算法流程：

1. 读入 a 和 b。
2. 对 a 和 b 的副本进行排序，检查它们是否包含相同的元素集。如果不是，输出 "NO"。
3. 将数值映射到排名 0..n-1，生成 a_perm 和 b_perm。
4. 使用树状数组分别计算 a_perm 和 b_perm 的逆序对数量 inv_a 和 inv_b。
5. 如果 inv_a % 2 == inv_b % 2，输出 "YES"。否则，输出 "NO"。

这样问题就解决啦，是不是很清晰了呢，喵~

代码实现喵~

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

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n), b(n);
    std::vector<int> a_copy(n);
    
    // 读入数组 a，并复制一份用于排序检查
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        a_copy[i] = a[i];
    }
    // 读入数组 b
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    // 复制一份 b 用于排序检查
    std::vector<int> b_copy = b;
    std::sort(a_copy.begin(), a_copy.end());
    std::sort(b_copy.begin(), b_copy.end());

    // 基础检查：如果两个数组包含的元素集不同，则不可能成功
    if (a_copy != b_copy) {
        std::cout << "NO\n";
        return;
    }

    // 问题转化：将具体数值映射到它们的排名 (0, 1, ..., n-1)
    // 这样可以忽略具体数值，只关注排列结构
    std::map<int, int> val_to_rank;
    for (int i = 0; i < n; ++i) {
        val_to_rank[a_copy[i]] = i;
    }

    // 根据排名生成新的排列数组 a_perm 和 b_perm
    std::vector<int> a_perm(n), b_perm(n);
    for (int i = 0; i < n; ++i) {
        a_perm[i] = val_to_rank[a[i]];
        b_perm[i] = val_to_rank[b[i]];
    }

    // 使用 Lambda 表达式定义一个计算逆序对的函数
    // 这里使用了树状数组 (Fenwick Tree) 的方法，效率很高喵~
    auto count_inversions = [&](const std::vector<int>& p) {
        int p_size = p.size();
        if (p_size <= 1) {
            return 0LL; // 长度为0或1的数组没有逆序对
        }
        
        // ft 是我们的树状数组
        std::vector<int> ft(p_size + 1, 0);
        
        // update 操作：在 idx 位置增加 val
        auto update = [&](int idx, int val) {
            for (++idx; idx <= p_size; idx += idx & -idx) {
                ft[idx] += val;
            }
        };
        
        // query 操作：查询 [0, idx] 区间的前缀和
        auto query = [&](int idx) {
            int sum = 0;
            if (idx < 0) return 0;
            for (++idx; idx > 0; idx -= idx & -idx) {
                sum += ft[idx];
            }
            return sum;
        };

        long long inversions = 0;
        // 从后往前遍历排列
        for (int i = p_size - 1; i >= 0; --i) {
            // 对于 p[i]，查询在它右边（因为是从后往前遍历，所以是已经处理过的数）
            // 且比它小的数的个数。这就是以 p[i] 为较大数的逆序对数量
            inversions += query(p[i] - 1);
            // 将 p[i] 加入到树状数组中，表示这个数已经出现过了
            update(p[i], 1);
        }
        return inversions;
    };

    // 分别计算 a_perm 和 b_perm 的逆序对数量
    long long inv_a = count_inversions(a_perm);
    long long inv_b = count_inversions(b_perm);

    // 核心判断：只有当两个排列的逆序对数量奇偶性相同时，才可能通过操作使它们一致
    if ((inv_a % 2) == (inv_b % 2)) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\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 log N) 的说

  • 排序检查需要 O(N log N)。
  • 构建 val_to_rank 的 map 需要 O(N)。
  • 生成 a_perm 和 b_perm 需要 O(N)。
  • 计算逆序对是核心部分。对于每个排列，我们需要遍历 N 个元素，每次遍历在树状数组上进行一次 query 和 update 操作，这两个操作的复杂度都是 O(log N)。所以计算一次逆序对是 O(N log N)。我们计算了两次。
  • 总的时间复杂度由排序和计算逆序对决定，所以是 O(N log N) 呐。

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

  • 我们需要存储 a, b, a_copy, b_copy, a_perm, b_perm 这些数组，都需要 O(N) 的空间。
  • val_to_rank 这个 map 也需要 O(N) 的空间。
  • 树状数组 ft 也需要 O(N) 的空间。
  • 所以总的空间复杂度是 O(N)。

知识点与总结

这道题真是一次有趣的思维体操呢，喵~ 它教会了我们几件重要的事情：

1. 问题转化与抽象: 将具体数值问题转化为排列问题，是解决这类问题的关键一步。这能帮助我们剥离不重要的信息，专注于问题的核心结构。
2. 寻找不变量: 在允许进行某种操作的题目中，寻找操作过程中的“不变量”是一种非常强大的解题思想。这道题的不变量就是两个排列逆序对奇偶性的相对关系。
3. 排列的奇偶性: 这是一个重要的数学概念。记住“一次交换会改变排列的奇偶性”这个性质，在很多组合和算法问题中都非常有用！
4. 数据结构的应用: 高效地计算逆序对数量是本题的实现关键。树状数组（或线段树、归并排序）是解决这个问题的标准工具，一定要熟练掌握哦。

希望这篇题解能帮助到你！继续加油，你一定能解决更多有趣的题目的，喵~！