D. Yet Another Inversions Problem - 题解

比赛与标签

比赛: Codeforces Round 917 (Div. 2) 标签: combinatorics, data structures, dp, implementation, math, number theory 难度: *2300

题目大意喵~

主人你好呀~！这道题是这样的呐：

我们有两个排列，一个叫做 p，长度是 n，里面是 1 到 2n-1 之间的 n 个不同的奇数。另一个叫做 q，长度是 k，里面是 0 到 k-1 的一个排列。

然后呢，我们要根据 p 和 q 来构造一个超级长的数组 a，它的长度是 n*k。构造规则是：a 数组的第 i*k + j 个元素 a[i*k+j] 的值等于 p[i] * 2^(q[j])。这里 0 <= i < n, 0 <= j < k。

你可以把数组 a 想象成 n 个块，第 i 个块是由 p[i] 分别乘以 2 的 q[0], q[1], ..., q[k-1] 次方得到的。

我们的任务就是，计算这个新数组 a 中有多少个逆序对，也就是有多少对索引 (i, j) 满足 i < j 并且 a[i] > a[j]。因为答案可能很大，所以要对 998244353 取模哦~

解题思路详解的说

这道题看起来有点吓人，数组 a 那么长，直接去算逆序对肯定会超时的说！但是不要怕，让本喵来带你一步步拆解它，喵~

解决这类问题的关键思路是 分类讨论 和 贡献法！我们可以把 a 数组中的逆序对分成两大类：

块内逆序对：逆序对的两个元素在 a 数组的同一个块里。
块间逆序对：逆序对的两个元素在 a 数组的不同块里。

只要分别算出这两部分的数量再加起来，就是总答案啦！

Part 1: 块内逆序对 (Intra-block Inversions) 呐~

我们先来看看比较简单的块内逆序对。第 i 个块的元素是 [p[i] * 2^(q[0]), p[i] * 2^(q[1]), ..., p[i] * 2^(q[k-1])]。

在这个块里，任意两个元素 a[i*k + j1] 和 a[i*k + j2]（假设 j1 < j2），它们的大小关系是 p[i] * 2^(q[j1]) 和 p[i] * 2^(q[j2]) 的比较。因为 p[i] 是个正奇数，所以我们可以直接约掉它，大小关系就变成了 2^(q[j1]) 和 2^(q[j2]) 的比较。

所以，a[i*k + j1] > a[i*k + j2] 当且仅当 q[j1] > q[j2]。这说明，第 i 个块内的逆序对数量，就等于排列 q 自身的逆序对数量！

设 inv(q) 是排列 q 的逆序对数量。因为我们有 n 个这样的块，每个块的结构都一样，所以块内逆序对的总数就是 n * inv(q)。

计算一个排列的逆序对是个经典问题，用树状数组（Fenwick Tree）或者归并排序就可以在 O(k log k) 的时间里解决。这里我们用树状数组会很方便哦。

Part 2: 块间逆序对 (Inter-block Inversions) 的奇妙冒险!

这部分是重头戏，有点小复杂，但跟上本喵的思路就没问题啦！我们需要计算满足 i1 < i2 且 a[i1*k + j1] > a[i2*k + j2] 的四元组 (i1, j1, i2, j2) 的数量。

直接去数四元组太难了，我们换个角度，用 贡献法 来思考。块间逆序对的总数可以写成： Sum_{0 <= i1 < i2 < n} Sum_{0 <= j1, j2 < k} [p[i1] * 2^(q[j1]) > p[i2] * 2^(q[j2])] （[] 是艾弗森括号，条件为真时值为1，否则为0）

这个求和顺序不好处理，我们交换一下求和的顺序： Sum_{0 <= j1, j2 < k} Sum_{0 <= i1 < i2 < n} [p[i1] * 2^(q[j1]) > p[i2] * 2^(q[j2])]

我们来分析 [] 里的不等式：p[i1] / p[i2] > 2^(q[j2] - q[j1])。令 d = q[j2] - q[j1]，不等式变为 p[i1] / p[i2] > 2^d。令 N(d) 表示满足 i1 < i2 且 p[i1] / p[i2] > 2^d 的 (i1, i2) 对数。

那么总数可以写成 Sum_{0 <= j1, j2 < k} N(q[j2] - q[j1])。我们再按 d 的值来分组，上式就等于 Sum_d C(d) * N(d)，其中 C(d) 是满足 q[j2] - q[j1] = d 的 (j1, j2) 对数。

一个神奇的发现, 喵!q 是 0 到 k-1 的一个排列，所以 {q[0], ..., q[k-1]} 这个集合就是 {0, ..., k-1}。因此，所有 (q[j1], q[j2]) 对构成的集合，就和所有 (v1, v2)（其中 v1, v2 来自 {0, ..., k-1}）对的集合是一样的！所以 C(d) 的值只和 k 与 d 有关，和 q 的具体排列无关！C(d) 就是满足 v2 - v1 = d 且 0 <= v1, v2 < k 的整数对 (v1, v2) 的数量。这个很容易计算，答案是 k - abs(d)。

所以，块间逆序对总数 = Sum_{d=-(k-1)}^{k-1} (k - abs(d)) * N(d)。

Part 3: 计算 N(d) 的说!

现在问题变成了如何计算 N(d)。 p 数组里的数都是 1 到 2n-1 之间的奇数，所以 1/(2n-1) <= p[i1]/p[i2] <= 2n-1。我们定义一个边界 D_BOUND，使得 2^(D_BOUND) > 2n-1。一个简单的取法是 D_BOUND = floor(log2(2n-1)) + 1。

接下来，我们对 d 的范围进行分类讨论：

Case A: d >= D_BOUND 此时 2^d >= 2^D_BOUND > 2n-1。因为 p[i1]/p[i2] <= 2n-1，所以 p[i1]/p[i2] > 2^d 永远不成立。因此，N(d) = 0。
Case B: d <= -D_BOUND 令 e = -d，则 e >= D_BOUND。不等式变为 p[i1] > p[i2] * 2^(-d)，即 p[i1] * 2^e > p[i2]。因为 p[i1] >= 1，所以 p[i1] * 2^e >= 2^e >= 2^D_BOUND > 2n-1。而 p[i2] <= 2n-1。所以 p[i1] * 2^e > p[i2] 永远成立！ N(d) 就等于所有 i1 < i2 的对数，即 n * (n-1) / 2。这部分的贡献是 Sum_{d=-(k-1)}^{-D_BOUND} (k - abs(d)) * (n*(n-1)/2)。这是一个等差数列求和，可以 O(1) 算出来。
Case C: |d| < D_BOUND 对于这些 "不大不小" 的 d，我们必须老老实实计算 N(d) 了。 N(d) 是满足 i1 < i2 且 p[i1] > p[i2] * 2^d 的对数。我们可以遍历 i2 从 0 到 n-1，在每一步计算有多少个 i1 < i2 满足条件。这又是一个可以用树状数组解决的问题！对于固定的 d 和 i2，我们要找的是在 p[0...i2-1] 中，有多少个元素大于 p[i2] * 2^d。我们可以用一个大小为 2n 的树状数组来维护 p 数组中已经出现过的数字。对于每个 d 在 (-D_BOUND, D_BOUND) 范围内：
1. 清空树状数组（或者撤销上次的修改）。
2. 初始化 N_d = 0。
3. 遍历 i 从 0 到 n-1 (作为 i2)：
  - 计算阈值 threshold = p[i] * 2^d（注意 d<0 时是整除）。
  - 用树状数组查询在 p[0...i-1] 中大于 threshold 的元素个数，并累加到 N_d。
  - 将 p[i] 加入树状数组。
4. 将 (k - abs(d)) * N_d 加入总答案。

最后把 Part 1 和 Part 2 的结果加起来取模，就是最终答案啦！

代码实现喵~

cpp

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

using namespace std;

const int MOD = 998244353;

// 快速幂，用于计算模逆元
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 费马小定理求模逆元
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// 树状数组（Fenwick Tree）结构体，喵~
struct FenwickTree {
    vector<int> bit;
    int size;

    FenwickTree(int sz) : size(sz), bit(sz + 1, 0) {}

    // 单点增加
    void add(int idx, int delta) {
        for (; idx <= size; idx += idx & -idx) {
            bit[idx] += delta;
        }
    }

    // 查询前缀和
    int query(int idx) {
        if (idx <= 0) return 0;
        if (idx > size) idx = size;
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += bit[idx];
        }
        return sum;
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    vector<int> q(k);
    for (int i = 0; i < k; ++i) cin >> q[i];

    long long total_inversions = 0;

    // Part 1: 计算块内逆序对
    long long inv_q = 0;
    if (k > 0) {
        FenwickTree ft_q(k);
        for (int i = 0; i < k; ++i) {
            // q[i] 与前面比它大的数构成逆序对
            // 总共有 i 个数在前面，其中 ft_q.query(q[i]+1) 个数小于等于 q[i]
            inv_q += i - ft_q.query(q[i] + 1);
            ft_q.add(q[i] + 1, 1); // 将 q[i] 加入树状数组
        }
        inv_q %= MOD;
    }
    total_inversions = (long long)n * inv_q % MOD;

    // Part 2: 计算块间逆序对
    long long inter_block_inv = 0;
    
    // 计算 D_BOUND，使得 2^D_BOUND > 2n-1
    int D_BOUND = 0;
    if (n > 0) {
        long long val = 2LL * n - 1;
        if (val <= 0) val = 1;
        while ((1LL << D_BOUND) <= val) {
            D_BOUND++;
        }
    }

    // Case d <= -D_BOUND 的情况
    if (k > D_BOUND) {
        long long num_terms = k - D_BOUND; // d 从 -k+1 到 -D_BOUND
        long long n_pairs = (long long)n * (n - 1) / 2 % MOD;
        // (k-D_BOUND) + (k-D_BOUND-1) + ... + 1 的和
        long long sum_coeffs = num_terms % MOD * ((num_terms + 1) % MOD) % MOD;
        sum_coeffs = sum_coeffs * modInverse(2) % MOD;
        inter_block_inv = (inter_block_inv + sum_coeffs * n_pairs) % MOD;
    }

    // Case |d| < D_BOUND 的情况
    FenwickTree ft_p(2 * n);
    vector<int> modified_indices; // 用于高效重置树状数组

    for (int d = -D_BOUND + 1; d < D_BOUND; ++d) {
        long long coeff = k - abs(d);
        if (coeff <= 0) continue;

        long long N_d = 0;
        // 遍历 p 数组，计算 N(d)
        if (d >= 0) { // p[i1] > p[i2] * 2^d
            for (int i = 0; i < n; ++i) {
                long long threshold = (long long)p[i] * (1LL << d);
                long long count = 0;
                if (threshold < 2 * n) {
                    // 查询已插入的 p 中 > threshold 的个数
                    count = i - ft_p.query(threshold);
                } else {
                    // 如果 threshold 太大，所有已插入的 p 都小于它
                    count = i;
                }
                N_d += count;
                ft_p.add(p[i], 1);
                modified_indices.push_back(p[i]);
            }
        } else { // d < 0, p[i1] > p[i2] / 2^(-d)
            int e = -d;
            for (int i = 0; i < n; ++i) {
                long long threshold = p[i] / (1LL << e);
                // 查询已插入的 p 中 > threshold 的个数
                long long count = i - ft_p.query(threshold);
                N_d += count;
                ft_p.add(p[i], 1);
                modified_indices.push_back(p[i]);
            }
        }
        N_d %= MOD;

        // 撤销本次对树状数组的修改，准备下一次 d 的计算
        for (int idx : modified_indices) {
            ft_p.add(idx, -1);
        }
        modified_indices.clear();

        inter_block_inv = (inter_block_inv + coeff * N_d) % MOD;
    }

    total_inversions = (total_inversions + inter_block_inv) % MOD;
    if (total_inversions < 0) total_inversions += MOD;

    cout << total_inversions << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(k log k + n * log(n) * log(n)) 的说。
- 计算 inv(q) 使用树状数组，需要 O(k log k)。
- 计算 D_BOUND 需要 O(log n)。
- 处理 d <= -D_BOUND 的情况是 O(1)。
- 处理 |d| < D_BOUND 的情况是核心。d 的循环次数是 2 * D_BOUND - 1，大约是 O(log n)。循环内部，我们遍历 p 数组（n 个元素），每次对树状数组进行查询和更新，操作复杂度是 O(log n)。所以这部分的复杂度是 O(D_BOUND * n * log n)，即 O(n * (log n)^2)。
- 考虑到多组测试用例的 n 和 k 的总和限制，这个复杂度是可以通过的。
空间复杂度: O(n + k) 的说。
- 我们需要存储 p 和 q 数组，空间是 O(n + k)。
- 树状数组 ft_q 需要 O(k) 空间，ft_p 需要 O(n) 空间。
- 总的空间复杂度就是 O(n + k)。

知识点与总结, 喵!

这真是一道融合了多种思想的有趣题目呀！主人你做出来了吗？我们来总结一下吧~

分治与贡献法: 这是解题的灵魂！将一个复杂的大问题（计算 nk*nk 数组的逆序对）分解成更小、更易于处理的子问题（块内和块间），然后对每个子部分计算其贡献，最终汇总。
树状数组 (Fenwick Tree): 它是我们强大的工具，无论是计算排列的逆序对，还是在动态过程中查询满足特定大小关系的元素数量，都非常高效，是每个算法竞赛选手必备的技能喵~
数学洞察力:
- 排列性质: 巧妙地利用 q 是一个排列，将对 q 的复杂计数问题 C(d) 转化为一个与具体排列无关的、简单的组合计数问题。
- 分类讨论: 根据 d 和 D_BOUND 的关系进行分类讨论，将无限的情况（看起来）归纳为三种有限的情形，极大地简化了计算。
- 等差数列: 在处理 d 很大的情况时，能发现贡献是一个等差数列求和，从而实现 O(1) 计算。

希望本喵的题解能帮到你哦！继续加油，享受解题的乐趣吧，喵~ 💕

D. Yet Another Inversions Problem - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路详解的说 ​

Part 1: 块内逆序对 (Intra-block Inversions) 呐~ ​

Part 2: 块间逆序对 (Inter-block Inversions) 的奇妙冒险! ​

Part 3: 计算 N(d) 的说! ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结, 喵! ​