daily pastebin goal
53%
SHARE
TWEET

Untitled

a guest Feb 19th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Merge-sort with inversion count - O(nlog n)
  2.  
  3. int n, inv;
  4. vector<int> v, ans;
  5.  
  6. void mergesort(vector<int> &v, int l, int r){
  7.     if(l == r) return;
  8.     int mid = (l+r)/2;
  9.     mergesort(v, l, mid), mergesort(v, mid+1, r);
  10.     int i = l, j = mid + 1, k = l;
  11.     while(i <= mid and j <= r){
  12.         if(v[i] > v[j]){
  13.             ans[k++] = v[j++];
  14.             inv += j-k;
  15.         }
  16.         else ans[k++] = v[i++];
  17.     }
  18.     while(i <= mid) ans[k++] = v[i++];
  19.     for(i = l; i < k; i++) v[i] = ans[i];
  20. }
  21.  
  22. //in main
  23. ans.resize(n);
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top