D. Inversion Counting - 题解

比赛与标签

比赛: Educational Codeforces Round 35 (Rated for Div. 2) 标签: brute force, math 难度: *1800

题目大意喵~

主人，这道题目是这样的呐：

首先，我们会得到一个长度为 n 的排列（也就是 1 到 n 这 n 个数字，每个都只出现一次组成的数组）。然后呢，我们需要处理 m 个询问。

每个询问会给我们两个数字 l 和 r，表示我们要把数组中从第 l 个位置到第 r 个位置的这一段整个翻转过来。

在每次翻转操作之后，我们都要判断一下，当前整个数组的逆序对总数是奇数还是偶数，然后输出 "odd" 或者 "even" 就可以啦。

逆序对是什么？就是一个数对 (i, j)，如果 i < j 但是 a[i] > a[j]，那它们就是一个逆序对啦。简单说就是大数跑到了小数的前面，破坏了队形！

解题思路的奇妙旅程~

嘿嘿，这道题看起来有点吓人，m 那么大，每次翻转都重新算一遍逆序对肯定会超时的说！O(m * n^2) 的复杂度，计算机会哭的！( TωT )

但是，主人请注意一个关键点：我们不需要知道逆序对的具体数量，只需要知道它的奇偶性！这是一个非常重要的突破口喵！

让我们来分析一下，翻转一个区间 [l, r] 会对逆序对的数量产生什么影响吧！

不受影响的区域：
- 如果一对数 (a[i], a[j]) 两个都在区间外面，它们的相对位置不变，逆序对状态当然也不变。
- 如果一个数在区间内，一个在区间外，它们的相对位置还是不变，逆序对状态也还是不变。
真正发生变化的区域：
- 只有当一对数 (a[i], a[j]) 两个都在要被翻转的区间 [l, r] 内部时，它们的相对位置才会改变！

好，那我们就聚焦在这个区间 [l, r] 上。设这个区间的长度是 L = r - l + 1。

在这个区间里，一共有多少对数呢？学过组合数学的我们知道，是从 L 个元素里选 2 个，也就是 C(L, 2) = L * (L - 1) / 2 对。我们把这个数量记作 T 好了。

现在，神奇的事情要发生了喵！对于区间内的任意一对数 (a[i], a[j])：

如果它原本是逆序对（a[i] > a[j]），翻转后，它们的位置互换，就不再是逆序对了。
如果它原本不是逆序对（a[i] < a[j]），翻转后，它们的位置互换，就变成了逆序对。

也就是说，翻转操作把区间内所有数对的逆序状态都给颠倒了！

假设原来区间内有 k 个逆序对，那么翻转后，这 k 个逆序对消失了，而原来不是逆序对的 T - k 对数，全都变成了新的逆序对。

所以，逆序对总数的变化量 Δ 就是：Δ = (新产生的) - (消失的) = (T - k) - k = T - 2k。

我们关心的是逆序对总数奇偶性的变化，也就是 Δ 的奇偶性。 Δ mod 2 = (T - 2k) mod 2

因为 2k 永远是个偶数，所以 (T - 2k) mod 2 就等于 T mod 2！

结论揭晓！ 每次翻转操作，逆序对总数的奇偶性变化，只和被翻转区间的长度 L 有关！具体来说，就是加上了 T = L * (L - 1) / 2 这么多。我们只需要判断 T 是奇数还是偶数，然后更新我们维护的奇偶性状态就好啦！

所以，我们的算法是：

初始化：先用 O(n^2) 的时间暴力计算出最开始的逆序对总数的奇偶性。n 最大是 1500，1500^2 大约是 225 万，完全可以接受。
处理询问：对于每个询问 (l, r)，我们 O(1) 计算出 L = r - l + 1 和 T = L * (L - 1) / 2。如果 T 是奇数，就翻转一下我们记录的奇偶性状态。

这样，总的时间复杂度就是 O(n^2 + m)，完美解决问题，喵~！

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <numeric> // reverse在这里其实没用到，但有时会用

using namespace std;

int main() {
    // 提高输入输出效率，猫娘的小习惯~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    // 第一步：计算初始排列的逆序对总数的奇偶性
    // parity = 0 表示偶数，parity = 1 表示奇数
    int parity = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 发现一个逆序对，就翻转一次奇偶性
            if (a[i] > a[j]) {
                parity ^= 1; // 使用异或操作来切换 0 和 1
            }
        }
    }

    int m;
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        
        // 计算被翻转区间的长度
        int L = r - l + 1;
        
        // 计算这个区间内总共有多少对元素
        // 这个 T 就是逆序对数量变化的奇偶性的关键！
        long long T = (long long)L * (L - 1) / 2;
        
        // 如果 T 是奇数，那么总的奇偶性就会改变
        // T & 1 是判断奇偶性的高效写法，等价于 T % 2
        if ((T & 1) == 1) {
            parity ^= 1;
        }
        
        // 根据当前的奇偶性状态输出结果
        if (parity) {
            cout << "odd\n";
        } else {
            cout << "even\n";
        }
    }

    return 0;
}

复杂度分析的说

时间复杂度: O(n² + m) 的说。
- O(n^2) 来自于一开始计算初始逆序对奇偶性的双重循环。
- O(m) 来自于处理 m 个询问，每个询问都只花了 O(1) 的常数时间，真是太快啦！
空间复杂度: O(n) 的说。
- 我们主要用了一个 vector 来存储这个排列，所以空间开销是线性的。

猫娘的小总结~

这道题真是太有趣了，它教会了我们一个重要的思想，喵~

关注问题本质：题目要求判断奇偶性，而不是具体数值。这常常是简化问题的信号！当看到“奇偶性”时，可以多往 mod 2 和位运算（比如异或 ^）的方向思考。
数学的力量：通过一点点数学推导，我们发现逆序对数量的变化量 Δ = T - 2k，从而把问题简化为只与区间长度 L 有关。这就像找到了解开谜题的魔法咒语！
分步解决：先处理好初始状态（O(n^2)），再高效地处理每次更新（O(1)）。这种“预处理 + 快速查询”的模式在算法竞赛中非常常见。

希望本猫娘的讲解能让主人豁然开朗！下次遇到类似的题目，也要记得从奇偶性这个小切口入手哦！加油，喵~！(๑•̀ㅂ•́)و✧

D. Inversion Counting - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路的奇妙旅程~ ​

代码实现喵~ ​

复杂度分析的说 ​

猫娘的小总结~ ​