역쌍(Inversion Pair)이란 주어진 양의 정수 배열에서 인덱스 i가 j보다 작으면서 값은 a[i]가 a[j]보다 큰 경우, 즉 i < j && a[i] > a[j]를 만족하는有序对(순서쌍)를 의미한다.
这类 문제를 풀 때 가장 먼저 떠올리는 방법은 병합 정렬을 이용하는 것이다. 그러나 今回は 펜윅 트리(Fenwick Tree) 또는 BIT(Binary Indexed Tree)라는 자료구조를 활용하여求解할 수 있다는 점을 다루고자 한다.
케이스 1: 배열이 순열(Permutation)인 경우
입력된 배열이 순열이라는 것은 중복된 값이 없다는 뜻이며, 최대값이 n으로 비교적 작은 상황을 의미한다. 이러한 경우에는 문제를 역동적으로 전환할 수 있다.
мысли는 다음과 같다: 배열을 왼쪽부터 오른쪽으로スキャン하면서, 현재까지 등장한 숫자들의 빈도를 펜윅 트리에 저장한다. 특정 위치의 값을 1씩 증가시키는 단일 수정 연산과 특정 범위의 합을 구하는 구간 查询 연산이 핵심이다.
여기서 중요한 테크닉은 다음과 같다. 일반적으로 펜윅 트리는 1부터 x까지의 합인 前綴합을 구하는 데 특화되어 있다. 그러나 역쌍을 구하려면 현재 위치 이후에 등장하는 숫자들의 개수, 즉 後綴합이 필요하다. 이를 해결하기 위해 입력값을 변환한다. a[i] = n + 1 - a[i]와 같이 변환하면, 원래의 "이후에 큰 값" 문제가 "이전에 작은 값" 문제로 바뀌어 일반적인 前綴합 查询으로求解할 수 있다.
구현 코드는 다음과 같다:
1 #include <bits/stdc++.h>
2 #define FASTIO ios::sync_with_stdio(false);cin.tie(nullptr);
3 using namespace std;
4
5 template <typename Type>
6 class FenwickTree {
7 private:
8 vector<Type> tree;
9 int size;
10 public:
11 explicit FenwickTree(int n) : size(n) {
12 tree.resize(n);
13 }
14
15 void add(int position, Type value) {
16 while (position < size) {
17 tree[position] += value;
18 position |= (position + 1);
19 }
20 }
21
22 Type sum(int position) {
23 Type result{};
24 while (position >= 0) {
25 result += tree[position];
26 position = (position & (position + 1)) - 1;
27 }
28 return result;
29 }
30
31 Type rangeSum(int left, int right) {
32 return sum(right) - sum(left - 1);
33 }
34 };
35
36 int main() {
37 FASTIO;
38 int length;
39 cin >> length;
40
41 FenwickTree<int> bit(length + 1);
42 long long inversionCount = 0;
43
44 for (int i = 1; i <= length; i++) {
45 int value;
46 cin >> value;
47 value = length + 1 - value;
48 inversionCount += bit.sum(value);
49 bit.add(value, 1);
50 }
51
cout << inversionCount << '\n';
52 return 0;
53 }
케이스 2: 배열에 중복이 있거나 값의 범위가 큰 경우
실제 문제에서는 배열이 순열이 아닐 수 있다. 즉, 동일한 값이 여러 번 등장하거나 값의 범위가 10^9와 같이 매우 클 수 있다. 이 경우 펜윅 트리의 인덱스로 값을 직접 사용할 수 없으므로, 별 처리가 필요하다.
핵심 아이디어는 실제 값의 크기보다 상대적인 크기 관계만 있으면 된다는 점이다. 따라서 이산화(Discretization)를 수행하여 값을 1부터 n 사이의 연속된 정수로 변환할 수 있다.
중복 값 처리에 주의해야 한다. 동일한 값이 여러 위치에 존재할 경우, 단순히 크기순으로만 정렬하면 어떤 원소를 先으로 처리하느냐에 따라 답이 달라질 수 있다. 이를 해결하기 위해 이산화 시 값的大小을 첫 번째 키, 원래 배열에서의 出現 순서를 두 번째 키로 사용하여 정렬한다. 이렇게 하면 동일한 값은 원래 배열에서의 순서대로 처리되므로 중복으로 인한 과대 계산을 방지할 수 있다.
구현 코드는 다음과 같다:
1 #include <bits/stdc++.h>
2 #define FASTIO ios::sync_with_stdio(false);cin.tie(nullptr);
3 using namespace std;
4
5 template <typename Type>
6 class FenwickTree {
7 private:
8 vector<Type> tree;
9 int size;
10 public:
11 explicit FenwickTree(int n) : size(n) {
12 tree.resize(n);
13 }
14
15 void add(int position, Type value) {
16 while (position < size) {
17 tree[position] += value;
18 position |= (position + 1);
19 }
20 }
21
22 Type sum(int position) {
23 Type result{};
24 while (position >= 0) {
25 result += tree[position];
26 position = (position & (position + 1)) - 1;
27 }
28 return result;
29 }
30
31 Type rangeSum(int left, int right) {
32 return sum(right) - sum(left - 1);
33 }
34 };
35
36 struct Element {
37 int value;
38 int originalIndex;
39 };
40
41 bool compareElements(const Element& lhs, const Element& rhs) {
42 if (lhs.value == rhs.value) {
43 return lhs.originalIndex < rhs.originalIndex;
44 }
45 return lhs.value < rhs.value;
46 }
47
48 int main() {
49 FASTIO;
50 int length;
51 cin >> length;
52
53 vector<Element> elements(length + 1);
54 for (int i = 1; i <= length; i++) {
55 cin >> elements[i].value;
56 elements[i].originalIndex = i;
57 }
58
59 sort(elements.begin() + 1, elements.end(), compareElements);
60
61 vector<int> mapped(length + 1);
62 for (int i = 1; i <= length; i++) {
63 mapped[elements[i].originalIndex] = length + 1 - i;
64 }
65
66 FenwickTree<int> bit(length + 1);
67 long long inversionCount = 0;
68
69 for (int i = 1; i <= length; i++) {
70 inversionCount += bit.sum(mapped[i]);
71 bit.add(mapped[i], 1);
72 }
73
cout << inversionCount << '\n';
74 return 0;
75 }
이 알고리즘은 정적 문제를 동적으로 전환하는 사고방식을 잘 보여주는 좋은 예시이다. 배열을 한 번 순회하면서 필요한 정보를 실시간으로 구축해 나가는 방식은 다양한 문제에 응용될 수 있다.