Advertisement
joydip007x

Count Inversion in array

Apr 4th, 2020
558
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. #define ll long long
  5. ll tmp[100000+1000],v[100000+1000];
  6.  
  7. ll mergesort(ll low, ll high){
  8.    
  9.    if(low>=high) return 0;
  10.    int mid= (low+high)/ 2 , ax=0,by=0;
  11.    ax=mergesort(low,mid);
  12.    by=mergesort(mid+1,high);
  13.    ll ret=0;
  14.    int i=low , j=mid+1,k=low;
  15.    while(i<=mid and j<=high){
  16.         if( v[i]<=v[j] ) tmp[k++]=v[i++];
  17.         else{
  18.             tmp[k++]=v[j++];
  19.             ret+=abs(mid+1-i);
  20.         }
  21.    }
  22.    while(i<=mid)  tmp[k++]=v[i++];
  23.    while(j<=high)  tmp[k++]=v[j++];
  24.    for(int i=low ; i<=high ;i++) v[i]=tmp[i];
  25.    return 1LL*ret+ax+by;
  26. }
  27.  
  28. int main()
  29. {
  30.     ll n ;
  31.     cin>>n;
  32.     for(ll i= 0; i<n ; i++)
  33.     {
  34.         scanf("%lld",&v[i]);
  35.         tmp[i]=0;
  36.     }
  37.     cout<<mergesort(0,n-1);
  38.    
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement