Inversion Count using Merge sort


#1
int mod=1e9+7;
vector<int>v;

int Merge(int s1,int e1,int s2,int e2)
{
    vector<int>tmp;
    int sin=s1;
    int ein=e2;
    int ans=0;
    while(s1<=e1&&s2<=e2)
    {
        if(v[s1]<=v[s2])
        {
            tmp.push_back(v[s1++]);
           
        }
        else
        {   ans%=mod;
            ans+=(e1-s1+1);
            
            tmp.push_back(v[s2++]);
        }
        
    }
    while(s1<=e1)
    {
        tmp.push_back(v[s1++]);
    }
    while(s2<=e2)
    {
        tmp.push_back(v[s2++]);
    }
    
    if(tmp.size()!=ein-sin+1)
    {
        cout<<"FATAL ERROR";
        exit(0);
    }
    for(int i=sin;i<=ein;i++)
    {
        v[i]=tmp[i-sin];
    }
    ans%=mod;
    return ans;
    
}
int invCnt(int be,int en)
{
    if(be>=en)return 0;
    int a=0;
    int m=be+(en-be)/2;
    a+=invCnt(be,m);
    a%=mod;
    
    a+=invCnt(m+1,en);
    a%=mod;
    a+=Merge(be,m,m+1,en);
    a%=mod;
    return a;
    
}

int Solution::solve(vector<int> &A) {
    v=A;
    return invCnt(0,A.size()-1);
}