Inversion Count
unknown
c_cpp
5 months ago
1.9 kB
5
Indexable
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define using_fast_io \ ios_base::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr); typedef long long int llint; typedef unsigned long long int ullint; llint do_count(int arr[], int lo, int mid, int hi) { int n1 = mid - lo + 1; int n2 = hi - mid; vector<int> left(n1); vector<int> right(n2); int idx = lo; for (int i = 0; i < n1; i++) { left[i] = arr[idx]; idx++; } for (int i = 0; i < n2; i++) { right[i] = arr[idx]; idx++; } int left_pointer = 0, right_pointer = 0, main_pointer = lo; llint inv_cnt = 0; while (left_pointer < n1 && right_pointer < n2) { if (left[left_pointer] <= right[right_pointer]) { arr[main_pointer] = left[left_pointer]; left_pointer++; } else { arr[main_pointer] = right[right_pointer]; inv_cnt += n1 - left_pointer; right_pointer++; } main_pointer++; } while (left_pointer < n1) { arr[main_pointer] = left[left_pointer]; left_pointer++; main_pointer++; } while (right_pointer < n2) { arr[main_pointer] = right[right_pointer]; right_pointer++; main_pointer++; } return inv_cnt; } llint inversion_count(int arr[], int lo, int hi) { llint to_return = 0; if (lo < hi) { int mid = lo + (hi - lo) / 2; to_return += inversion_count(arr, lo, mid); to_return += inversion_count(arr, mid + 1, hi); to_return += do_count(arr, lo, mid, hi); } return to_return; } void soln() { // taking an array as input int N; cin >> N; int arr[N]; for (int i = 0; i < N; i++) { cin >> arr[i]; } // fetching the inversion count llint solution = inversion_count(arr, 0, N - 1); cout << solution << endl; } int main() { using_fast_io; int t = 1; // cin >> t; while (t--) { soln(); } return 0; }
Editor is loading...
Leave a Comment