逆序k倍对·复盘

Posted on Edited on In

前言

本题同样由那位BUAA大佬分享。

不久前，我用树状数组解决了洛谷上的逆序对模板题 。因此，当我初见这道 逆序 k 倍对 时，第一反应便是：这一定是模板的变体，核心工具依然是那个熟悉的树状数组。然而，从模板代码到这道题的AC，并非简单的复制粘贴，而是一段充满思考的魔改之旅。本文旨在完整复盘，我是如何基于逆序对模板的思路，一步步识别问题差异、调整关键逻辑，最终将一份模板代码成功改造为本题的解答。

题目

题目描述

给定一个序列 a₁, a₂, …, aₙ 和一个正整数 k，如果 1 ≤ i < j ≤ n 且 aᵢ > k · aⱼ，我们就将 (i, j) 称作一个逆序 k 倍对。请你计算序列中逆序 k 倍对的个数。

输入格式

第一行两个正整数 n, k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10)。
第二行 n 个正整数 a₁, a₂, …, aₙ (1 ≤ aᵢ < 2³¹)。
为了提高区分度，对于得分占比 10% 的测试点，我们保证 1 ≤ n ≤ 100。

输出格式

一行一个非负整数，表示序列中逆序 k 倍对的个数。

输入样例

1
2
5 2
5 4 3 2 1

输出样例

1
4

题目分析

首先肯定要从那道经典的逆序对模板题开始分析。它的问题是统计 i < j 且 a[i] > a[j] 的数对。我当时AC的思路是：

  • 从左到右遍历数组，对于每个数 a[j]。
  • 利用树状数组，查询在它之前已经出现过的数中，有多少个大于 a[j]。
  • 将这些查询结果累加，就是答案。
  • 查询结束后，再将 a[j] 本身的信息更新到树状数组中。

当时的AC代码如下：

点击展开/折叠 逆序对模板题AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
vector<int>a, b;

int Lowbit(int x){
	return x & -x;
}

ll Sum(int x, ll arr[]){
	ll ansSUM = 0;
	for(int i = x; i != 0; i -= Lowbit(i)){
		ansSUM += arr[i];
	}
	return ansSUM;
}

void Update(int x, int add, int size, ll arr[]){
	for(int i = x; i <= size; i += Lowbit(i)){
		arr[i] += add;
	}
	return;
}

int main(){
	cin >> n;
	a.reserve(n + 5);
	b.reserve(n + 5);
	for(int i = 1; i <= n; i++){
		int num;
		cin >> num;
		a.push_back(num);
		b.push_back(num);
	}
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	int size = b.size();
	ll c[size + 5] = {0}, ans[size + 5] = {0};
	int cnt = 0;
	for(int p : a){
		cnt++;
		int idx = lower_bound(b.begin(), b.end(), p) - b.begin() + 1;
		Update(idx, 1, size, c);
		Update(idx, cnt - Sum(idx, c), size, ans);
	}
	cout << Sum(size, ans);
	return 0;
}

这个框架非常清晰。现在，面对k倍逆序对，唯一的不同点，就是判断条件从 a[i] > a[j] 变成了 a[i] > k * a[j]。

这意味着，我的改造也必须围绕这个变化点展开。当我遍历到 a[j] 时，我需要查询的不再是比 a[j] 大的数，而是比 k * a[j] 大的数。

这个看似微小的变化，却直接影响了算法的基石——离散化。在原模板中，我们只需要对数组 a 中的值进行离散化。但现在，为了能查询 k * a[j] 的相关信息，我们必须将所有可能作为查询边界的 k * a[j] 也一并纳入离散化的范围。

这就是从模板到AC的关键一步：识别出查询目标的变化，并相应地扩大离散化的集合。

算法设计及实现

我的整个解题过程，可以看作是对逆序对模板代码的一次定向升级。

核心思路：模板的演进

  1. 继承模板框架：

    • 整体的算法流程完全继承自逆序对模板：遍历数组 -> 查询贡献 -> 更新数据 -> 累加结果。
    • 核心数据结构依然锁定为树状数组，因为它能高效地完成我们需要的单点更新和前缀和查询。
    • 由于 a[i] 的值域依然很大，离散化这一前置步骤也必须保留。

  2. 定位改造核心：查询目标的变化

    • 模板的查询逻辑是：贡献 = 总数 - 小于等于a[j]的个数。
    • 本题的查询逻辑变为：贡献 = 总数 - 小于等于k*a[j]的个数。
    • 这个k*a[j]就是本次改造需要处理的新元素。

  3. 升级离散化：

    • 模板：离散化集合仅包含 { a[1], a[2], ..., a[n] }。
    • 本题：离散化集合必须扩大，同时包含 { a[1], ..., a[n] } 和 { k*a[1], ..., k*a[n] }。因为树状数组的下标是基于离散化后的排名，我们既需要能更新 a[j] 对应的排名，也需要能查询 k*a[j] 对应的排名。将它们全部放入一个集合中进行离散化，才能建立统一的“度量衡”。

  4. 微调主逻辑

    • 在主循环中，对于当前元素 p (即a[j])：
      • 首先，找到 p 离散化后的排名 idx。
      • 然后，找到 k*p 离散化后的排名 idx2。
      • 计算贡献值：ans += cnt - Sum(idx2, c)。这里的 cnt 是已处理元素个数，Sum(idx2, c) 则是利用树状数组查到的、前面出现过且值小于等于 k*p 的元素个数。
      • 最后，执行和模板完全一样的更新操作：Update(idx, 1, size, c)，将 p 的出现次数记录到树状数组中。

可行性分析

这次“魔改”并没有改变算法的根本结构。

  • 时间复杂度:

    • 离散化集合的大小最多变为 2n。排序的复杂度依然是 O(n log n)。
    • 主循环中，树状数组和 lower_bound 的操作复杂度仍为 O(log n)。
    • 总时间复杂度保持在 O(n log n)，完全可以通过。

  • 空间复杂度:

    • 辅助数组 b 和树状数组 c 的大小变为原来的两倍左右，空间复杂度依然是 O(n)。

  • 结论：
    通过精准地定位差异并对离散化这一关键步骤进行升级，我们成功地将逆序对模板适配到了新问题上，方案高效可行。

实现

最终的AC代码，清晰地保留了逆序对模板的骨架，但在离散化的部分，能明显看到为了适应新规则而做的扩展。

点击展开/折叠 最终AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, k;
ll ans;
vector<int>a, b;

int Lowbit(int x){
	return x & -x;
}

ll Sum(int x, ll arr[]){
	ll ansSUM = 0;
	for(int i = x; i != 0; i -= Lowbit(i)){
		ansSUM += arr[i];
	}
	return ansSUM;
}

void Update(int x, int add, int size, ll arr[]){
	for(int i = x; i <= size; i += Lowbit(i)){
		arr[i] += add;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	a.reserve(n + 5);
	b.reserve(2 * n + 5);
	for(int i = 1; i <= n; i++){
		int num;
		cin >> num;
		a.push_back(num);
		b.push_back(num);
		b.push_back(k * num);
	}
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	int size = b.size();
	ll c[size + 5] = {0};
	ll cnt = 0;
	for(int p : a){
		cnt++;
		int idx = lower_bound(b.begin(), b.end(), p) - b.begin() + 1;
		int idx2 = lower_bound(b.begin(), b.end(), p * k) - b.begin() + 1;
		Update(idx, 1, size, c);
		ans += cnt - Sum(idx2, c);
	}
	cout << ans;
	return 0;
}

代码对比

整个改造过程实际只涉及两个关键环节。

1. 扩展离散化集合

模板代码：仅收集原数组中的值。

1
2
3
4
5
6
7
// 离散化集合 b 只需包含 a 内的值
for(int i = 1; i <= n; i++){
    int num;
    cin >> num;
    a.push_back(num);
    b.push_back(num);
}

本题代码：同时收集原数值与其 k 倍值。

1
2
3
4
5
6
7
8
// 离散化集合 b 必须同时包含 a 内的值及其 k 倍
for(int i = 1; i <= n; i++){
    ll num;
    cin >> num;
    a.push_back(num);
    b.push_back(num);
    b.push_back(k * num); // 【改动】为查询 k*p 预作准备
}

原因：树状数组需要查询 k*p 的排名，因此必须在一开始就将所有可能的 k*p 值纳入离散化，以建立统一的排名体系。

2. 变更查询边界

模板代码：查询大于 p 的元素个数。

1
2
3
4
5
6
7
8
9
10
for(int p : a){
    // 查询和更新都使用 p 自身的排名
    int idx = lower_bound(b.begin(), b.end(), p) - b.begin() + 1;
    
    // 查询边界是 p 本身
    ans += cnt - Sum(idx, c);
    
    Update(idx, 1, size, c);
    cnt++;
}

本题代码：查询大于 k*p 的元素个数。

1
2
3
4
5
6
7
8
9
10
11
12
for(ll p : a){
    // 更新时用 p 的排名
    int idx = lower_bound(b.begin(), b.end(), p) - b.begin() + 1;
    // 【改动】计算新的查询边界 k*p 的排名
    int idx2 = lower_bound(b.begin(), b.end(), p * k) - b.begin() + 1;
    
    // 【改动】使用新的排名 idx2 进行查询
    ans += cnt - Sum(idx2, c);
    
    Update(idx, 1, size, c);
    cnt++;
}

原因：题目的核心条件从 > p 变为 > k*p，因此计算贡献时，传入 Sum 函数的参数，必须是 k*p 对应的排名，而非 p 的排名。

P.S. 例行在最后放上做题手稿

总结

  1. 模型识别与套用：将新问题关联到已知的算法模型（本题的逆序对模板），以此为基础快速构建解题框架。
  2. 分析核心差异：精准定位问题变体的关键不同点。本题的核心差异在于判断条件从 a[i] > a[j] 变更为 a[i] > k * a[j]。
  3. 模块化调整：根据核心差异，修改算法中受影响的模块。此题中，查询条件的变更，直接决定了离散化的数据集合必须相应地扩展。
  4. 理解功能而非形式：掌握算法中每个模块的功能目的是解决问题的关键。这使得我们能根据问题变化，对模板进行有效调整，而不是进行无效的生搬硬套。