Introduction

This problem was also shared by that skilled programmer from BUAA.

Not long ago, I used a Fenwick tree to solve Luogu’s standard inversion-counting problem. So when I first saw k-multiple inversion pairs, my immediate reaction was: this has to be a variation on the template, and the core tool will still be that familiar Fenwick tree. But getting from the template code to an accepted solution was no simple copy-and-paste job. It was a journey of thoughtful hacking and adapting. In this post, I want to review the whole process: how I started with the inversion-counting template, identified the differences step by step, adjusted the key logic, and ultimately adapted the template into a solution to this problem.

The Problem

Description

Given a sequence a₁, a₂, …, aₙ and a positive integer k, call (i, j) a k-multiple inversion pair if 1 ≤ i < j ≤ n and aᵢ > k · aⱼ. Calculate the number of k-multiple inversion pairs in the sequence.

Input

The first line contains two positive integers n, k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10).
The second line contains n positive integers a₁, a₂, …, aₙ (1 ≤ aᵢ < 2³¹).
To provide more differentiation in scoring, test cases worth 10% of the score guarantee 1 ≤ n ≤ 100.

Output

Print one nonnegative integer: the number of k-multiple inversion pairs in the sequence.

Sample Input

1
2
5 2
5 4 3 2 1

Sample Output

1
4

Analysis

The obvious starting point is that classic inversion-counting template problem. It asks us to count pairs with i < j and a[i] > a[j]. My accepted approach at the time was:

  • Traverse the array from left to right, considering each a[j].
  • Use a Fenwick tree to query how many numbers that have already appeared before it are greater than a[j].
  • Add up these query results to get the answer.
  • After querying, update the Fenwick tree with a[j] itself.

Here is the code that was accepted then:

Expand/collapse the accepted inversion-counting template code 
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;
}

The framework is very clear. Now, for k-multiple inversion pairs, the only difference is that the condition changes from a[i] > a[j] to a[i] > k * a[j].

That means my changes must center on this difference. When I reach a[j], I no longer need to query for numbers greater than a[j], but for numbers greater than k * a[j].

This seemingly tiny change directly affects the algorithm’s foundation: coordinate compression. In the original template, we only needed to compress the values in array a. Now, to query information involving k * a[j], we also need to include every k * a[j] that could serve as a query boundary in the compression set.

This is the crucial step from template to accepted solution: recognize the change in the query target, and expand the compression set accordingly.

Algorithm Design and Implementation

My entire solution process can be seen as a targeted upgrade of the inversion-counting template.

The Core Idea: Evolving the Template

  1. Keep the template’s framework:

    • The overall algorithm follows the inversion-counting template in full: traverse the array → query the contribution → update the data → accumulate the result.
    • The core data structure remains a Fenwick tree, because it efficiently supports the point updates and prefix-sum queries we need.
    • Since the range of a[i] is still large, coordinate compression must also remain as a preprocessing step.

  2. Locate the core change: the query target

    • The template’s query logic is 贡献 = 总数 - 小于等于a[j]的个数: contribution = total count − count of values less than or equal to a[j].
    • For this problem, it becomes 贡献 = 总数 - 小于等于k*a[j]的个数: contribution = total count − count of values less than or equal to k*a[j].
    • This k*a[j] is the new element that the adaptation needs to handle.

  3. Expand coordinate compression:

    • Template: The compression set contains only { a[1], a[2], ..., a[n] }.
    • This problem: The compression set must expand to include both { a[1], ..., a[n] } and { k*a[1], ..., k*a[n] }. Fenwick-tree indices are based on the compressed ranks: we need both to update the rank corresponding to a[j] and to query the rank corresponding to k*a[j]. Compressing them all in one set establishes a common scale.

  4. Adjust the main logic

    • For the current element p (that is, a[j]) in the main loop:
      • First, find p‘s compressed rank, idx.
      • Then find the compressed rank of k*p, idx2.
      • Calculate the contribution: ans += cnt - Sum(idx2, c). Here, cnt is the number of processed elements, and Sum(idx2, c) is the Fenwick-tree query for the number of previously encountered elements whose values are less than or equal to k*p.
      • Finally, perform exactly the same update as in the template: Update(idx, 1, size, c), recording an occurrence of p in the Fenwick tree.

Feasibility Analysis

This “hack” does not change the fundamental structure of the algorithm.

  • Time complexity:

    • The compression set grows to at most 2n elements. Sorting still takes O(n log n).
    • In the main loop, Fenwick-tree operations and lower_bound still take O(log n).
    • The overall time complexity remains O(n log n), comfortably sufficient for the problem.

  • Space complexity:

    • Auxiliary array b and Fenwick tree c become roughly twice as large, but space complexity is still O(n).

  • Conclusion:
    By identifying the exact difference and expanding the crucial coordinate-compression step, we successfully adapt the inversion-counting template to the new problem. The approach is efficient and feasible.

Implementation

The final accepted code clearly retains the skeleton of the inversion-counting template, with a visible expansion in the compression step to accommodate the new rule.

Expand/collapse the final accepted code 
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;
}

Comparing the Code

The whole adaptation really involves just two key parts.

1. Expanding the Compression Set

Template code: Collect only the values in the original array.

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);
}

Code for this problem: Collect both the original values and their k-fold values.

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 预作准备
}

Why: The Fenwick tree needs to query the rank of k*p, so all possible k*p values must be included in the compression set from the start to establish a unified ranking system.

2. Changing the Query Boundary

Template code: Query the number of elements greater than 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++;
}

Code for this problem: Query the number of elements greater than 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++;
}

Why: The core condition changes from > p to > k*p. So when calculating the contribution, the argument passed to Sum must be the rank corresponding to k*p, rather than the rank of p.

P.S. As usual, here are my handwritten working notes at the end.

My handwritten working notes

Diagram guide: The notes sketch Fenwick-tree prefix sums at the top, then work through the n=5, k=2 example and the combined compression set below. The handwritten “含” means “inclusive.”

Takeaways

  1. Recognize and apply a model: Connect a new problem to a known algorithmic model—the inversion-counting template here—and use it to build a solution framework quickly.
  2. Analyze the core difference: Identify precisely what makes the variant different. Here, the key change is from a[i] > a[j] to a[i] > k * a[j].
  3. Adjust the affected modules: Modify the parts of the algorithm affected by that difference. In this problem, the changed query condition directly requires a corresponding expansion of the coordinate-compression dataset.
  4. Understand function, not just form: Understanding the purpose of each part of an algorithm is the key to solving problems. It lets us adapt a template effectively as the problem changes, instead of forcing it onto a problem where it does not fit.