➤ Problem Link : DCEPC206
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll arr[100001];
ll ans=0;
ll tmp[100001];
ll cum[100001];
void Merge(ll l,ll m,ll r)
{
ll i=l,j=m+1,k=0;
for(ll j=l;j<=m;j++)
cum[j]=0;
cum[l]=arr[l];
for(ll j=l+1;j<=m;j++)
cum[j]=arr[j]+cum[j-1];
while(i<=m && j<=r)
{
if(arr[i]<arr[j])
{
if(i==l)
ans+=cum[m];
else
ans+=cum[m]-cum[i-1];
tmp[k++]=arr[j++];
}
else
tmp[k++]=arr[i++];
}
while(i<=m)
tmp[k++]=arr[i++];
while(j<=r)
tmp[k++]=arr[j++];
k=0;
for(i=l;i<=r;i++)
arr[i]=tmp[k++];
}
void MergeInv(ll l,ll r)
{
if(l<r)
{
ll m=(l+r)/2;
MergeInv(l,m);
MergeInv(m+1,r);
Merge(l,m,r);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ans=0;
for(ll i=0;i<n;i++)
cin>>arr[i];
MergeInv(0,n-1);
cout<<ans<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.