初级守护
#include <iostream> #include <vector> using namespace std; long long mergeAndCount(vector<int>& arr, int left, int mid, int right) { vector<int> temp(right - left + 1); int i = left, j = mid + 1, k = 0; 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, k = 0; i <= right; i++, k++) { arr[i] = temp[k]; } return inv_count; } long long mergeSortAndCount(vector<int>& arr, int left, int right) { long long inv_count = 0; if (left < right) { int mid = left + (right - left) / 2; inv_count += mergeSortAndCount(arr, left, mid); inv_count += mergeSortAndCount(arr, mid + 1, right); inv_count += mergeAndCount(arr, left, mid, right); } return inv_count; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> arr(n); for (int i = 0; i < n; ++i) { cin >> arr[i]; } cout << mergeSortAndCount(arr, 0, n - 1) << endl; return 0; }
