每日一道C++題：

問題：給定一個序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我們稱之為逆序對，求逆序對的數目。

要求：輸入第一行為n,表示序列長度，接下來的n行，第i+1行表示序列中的第i個數；輸出所有逆序對總數。

1. 暴力解法：
   • 思路：通過兩層循環，外層循環遍歷序列中的每一個元素，內層循環遍歷當前元素之后的所有元素。每次內層循環中，如果當前外層循環元素大于內層循環元素，就找到了一個逆序對，計數加1。

#include <iostream>
using namespace std;int main() {int n;cin >> n;int *arr = new int[n];for (int i = 0; i < n; i++) {cin >> arr[i];}int count = 0;for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {if (arr[i] > arr[j]) {count++;}}}cout << count << endl;delete[] arr;return 0;
}

• 首先讀取序列長度n，并動態分配一個大小為n的整數數組arr來存儲序列元素。
• 通過一個for循環讀取序列中的每一個數并存儲到數組中。
• 使用兩層嵌套的for循環來統計逆序對。外層循環從0到n - 2，內層循環從外層循環變量i的下一個位置到n - 1。如果arr[i] > arr[j]，則找到一個逆序對，count加 1。
• 最后輸出逆序對的總數，并釋放動態分配的數組內存。
• 時間復雜度：O(n 2 )，因為有兩層嵌套循環，對于長度為n的序列，總的操作次數是1+2+?+(n?1)= n(n?1)/2。
  ?
• 空間復雜度：O(n)，主要用于存儲輸入的序列。

2. 歸并排序優化解法：
   • 思路：歸并排序是一種分治算法，在合并兩個有序子數組的過程中，可以統計跨越兩個子數組的逆序對。將序列不斷地分成兩半，分別對左右兩半進行排序，然后合并兩個有序子數組。在合并過程中，如果左邊子數組的當前元素大于右邊子數組的當前元素，那么左邊子數組中從當前位置到末尾的所有元素都與右邊子數組的當前元素構成逆序對，記錄逆序對的數量并進行合并操作。

#include <iostream>
using namespace std;// 合并兩個有序數組并統計逆序對
long long merge(int arr[], int temp[], int left, int mid, int right) {int i = left; // 左子數組的起始索引int j = mid + 1; // 右子數組的起始索引int k = left; // 臨時數組的起始索引long long inv_count = 0;while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];inv_count += (mid - i + 1);}}// 復制左子數組剩余元素while (i <= mid) {temp[k++] = arr[i++];}// 復制右子數組剩余元素while (j <= right) {temp[k++] = arr[j++];}// 將臨時數組的內容復制回原數組for (i = left; i <= right; i++) {arr[i] = temp[i];}return inv_count;
}// 歸并排序主函數并統計逆序對
long long mergeSort(int arr[], int temp[], int left, int right) {long long inv_count = 0;if (left < right) {int mid = (left + right) / 2;// 遞歸地對左半部分和右半部分進行排序inv_count += mergeSort(arr, temp, left, mid);inv_count += mergeSort(arr, temp, mid + 1, right);// 合并兩個有序子數組并統計逆序對inv_count += merge(arr, temp, left, mid, right);}return inv_count;
}int main() {int n;cin >> n;int *arr = new int[n];int *temp = new int[n];for (int i = 0; i < n; i++) {cin >> arr[i];}long long result = mergeSort(arr, temp, 0, n - 1);cout << result << endl;delete[] arr;delete[] temp;return 0;
}

• merge函數用于合并兩個有序子數組并統計逆序對。left和right分別是當前要合并的子數組的左右邊界，mid是中間位置。通過比較左右子數組的元素，將較小的元素放入臨時數組temp中，并統計逆序對。
• mergeSort函數是歸并排序的主函數，通過遞歸地將數組分成兩半并排序，然后調用merge函數合并并統計逆序對。
• 在main函數中，讀取序列長度n，動態分配兩個數組arr和temp，arr用于存儲輸入序列，temp用于輔助合并操作。讀取序列元素后，調用mergeSort函數進行排序并統計逆序對，最后輸出結果并釋放內存。
• 時間復雜度：O(n log n)，因為歸并排序每次將數組分成兩半，共需要(log n)層遞歸，每層遞歸中合并操作的時間復雜度是O(n)。
• 空間復雜度：O(n)，主要用于存儲臨時數組temp。

3. 應用場景拓展：
   -排序算法穩定性分析：逆序對的數量與排序算法的穩定性有關。例如，冒泡排序、插入排序等穩定排序算法在排序過程中可以通過計算逆序對的減少來分析其工作過程。對于不穩定排序算法，如快速排序，了解逆序對的分布有助于優化算法，使其在某些情況下更接近穩定排序的效果。
   • 數據相似性度量：在數據挖掘和機器學習領域，逆序對的概念可以用于衡量兩個序列的相似性。如果兩個序列的逆序對數量較少，說明它們在某種程度上具有相似的順序結構。例如，在推薦系統中，可以通過比較用戶對不同物品的排序（形成序列）之間的逆序對數量，來判斷用戶興趣的相似性，進而為用戶提供更精準的推薦。

• 算法拓展：
  • 樹狀數組解法：可以使用樹狀數組來解決逆序對問題。樹狀數組是一種支持高效單點更新和區間查詢的數據結構。具體做法是，從序列的最后一個元素開始，依次將每個元素插入樹狀數組中，并查詢當前元素之前小于它的元素個數，累加這些個數就得到逆序對的總數。樹狀數組解法的時間復雜度也是 (O(n \log n))，但在某些情況下，其實現可能比歸并排序更簡潔，并且可以靈活地支持動態更新序列并重新計算逆序對。

#include <iostream>
#include <vector>// 樹狀數組類
class FenwickTree {
private:std::vector<int> bit; // 樹狀數組int n; // 數組大小// 計算lowbitint lowbit(int x) {return x & (-x);}public:// 初始化樹狀數組FenwickTree(int size) : n(size), bit(size + 1, 0) {}// 更新操作void update(int idx, int val) {while (idx <= n) {bit[idx] += val;idx += lowbit(idx);}}// 查詢操作int query(int idx) {int sum = 0;while (idx > 0) {sum += bit[idx];idx -= lowbit(idx);}return sum;}
};// 計算逆序對
long long countInversions(const std::vector<int>& arr) {int n = arr.size();// 離散化數組std::vector<int> sortedArr = arr;std::sort(sortedArr.begin(), sortedArr.end());std::vector<int> ranks(n);for (int i = 0; i < n; ++i) {ranks[i] = std::lower_bound(sortedArr.begin(), sortedArr.end(), arr[i]) - sortedArr.begin() + 1;}FenwickTree ft(n);long long invCount = 0;for (int i = n - 1; i >= 0; --i) {invCount += ft.query(ranks[i] - 1);ft.update(ranks[i], 1);}return invCount;
}int main() {int n;std::cin >> n;std::vector<int> arr(n);for (int i = 0; i < n; ++i) {std::cin >> arr[i];}std::cout << countInversions(arr) << std::endl;return 0;
}

• FenwickTree 類實現了樹狀數組的基本操作，包括初始化、更新和查詢。lowbit 函數用于計算一個數的二進制表示中最低位的 1 及其后面的 0 所構成的數值。

• countInversions 函數用于計算逆序對。首先對輸入數組進行離散化處理，將數組中的元素映射到 1 到 n 的范圍內，以便樹狀數組處理。然后從數組末尾開始，依次將每個元素的排名插入樹狀數組，并查詢小于該排名的元素個數，累加這些個數得到逆序對的總數。

  • 線段樹解法：線段樹同樣可以用于解決逆序對問題。線段樹是一種二叉樹結構，每個節點代表一個區間。通過在線段樹中插入元素并查詢區間信息，可以統計逆序對。線段樹的優點在于它能夠更靈活地處理區間相關的操作，比如在序列動態變化時，能夠高效地更新逆序對的統計結果。但線段樹的實現相對復雜，需要對其原理有深入理解。

#include <iostream>
#include <vector>
#include <algorithm>// 線段樹節點
struct SegmentTreeNode {int left, right;int count;SegmentTreeNode* leftChild;SegmentTreeNode* rightChild;SegmentTreeNode(int l, int r) : left(l), right(r), count(0), leftChild(nullptr), rightChild(nullptr) {}
};// 構建線段樹
SegmentTreeNode* buildSegmentTree(int left, int right) {SegmentTreeNode* root = new SegmentTreeNode(left, right);if (left < right) {int mid = (left + right) / 2;root->leftChild = buildSegmentTree(left, mid);root->rightChild = buildSegmentTree(mid + 1, right);}return root;
}// 更新線段樹
void updateSegmentTree(SegmentTreeNode* root, int idx) {if (root->left == root->right) {root->count++;return;}int mid = (root->left + root->right) / 2;if (idx <= mid) {updateSegmentTree(root->leftChild, idx);} else {updateSegmentTree(root->rightChild, idx);}root->count = root->leftChild->count + root->rightChild->count;
}// 查詢線段樹
int querySegmentTree(SegmentTreeNode* root, int left, int right) {if (root->left >= left && root->right <= right) {return root->count;}int mid = (root->left + root->right) / 2;if (right <= mid) {return querySegmentTree(root->leftChild, left, right);} else if (left > mid) {return querySegmentTree(root->rightChild, left, right);} else {return querySegmentTree(root->leftChild, left, mid) + querySegmentTree(root->rightChild, mid + 1, right);}
}// 計算逆序對
long long countInversions(const std::vector<int>& arr) {int n = arr.size();// 離散化數組std::vector<int> sortedArr = arr;std::sort(sortedArr.begin(), sortedArr.end());std::vector<int> ranks(n);for (int i = 0; i < n; ++i) {ranks[i] = std::lower_bound(sortedArr.begin(), sortedArr.end(), arr[i]) - sortedArr.begin();}SegmentTreeNode* root = buildSegmentTree(0, n - 1);long long invCount = 0;for (int i = 0; i < n; ++i) {invCount += querySegmentTree(root, ranks[i] + 1, n - 1);updateSegmentTree(root, ranks[i]);}return invCount;
}int main() {int n;std::cin >> n;std::vector<int> arr(n);for (int i = 0; i < n; ++i) {std::cin >> arr[i];}std::cout << countInversions(arr) << std::endl;return 0;
}

• SegmentTreeNode 結構體定義了線段樹的節點，每個節點包含區間范圍 left 和 right，以及該區間內元素的計數 count，還有左右子節點指針。
• buildSegmentTree 函數用于構建線段樹，遞歸地將區間劃分為左右子區間，并創建相應的節點。
• updateSegmentTree 函數用于更新線段樹，當插入一個新元素時，根據元素的位置更新相應節點的計數。
• querySegmentTree 函數用于查詢線段樹中指定區間內的元素計數。
• countInversions 函數首先對輸入數組進行離散化處理，然后從數組開頭開始，依次將每個元素插入線段樹，并查詢大于該元素的元素個數，累加這些個數得到逆序對的總數。