➤ Problem Link : INVCNT
👉 Hint : Think of some tree based data structure like segment tree or ordered_set in C++ STL
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll arr[200008];
ll st[40000001];
void build(ll v, ll l, ll r)
{
if(l==r)
{
st[v]=0;
return;
}
ll mid=(l+r)/2;
build(2*v,l,mid);
build(2*v+1,mid+1,r);
st[v]=st[2*v]+st[2*v+1];
}
void update(ll v, ll l, ll r, ll ind)
{
if(l==r)
{
st[v]=1;
return;
}
ll mid=(l+r)/2;
if(ind>=l && ind<=mid)
update(2*v,l,mid,ind);
else
update(2*v+1,mid+1,r,ind);
st[v]=st[2*v]+st[2*v+1];
}
ll query(ll v, ll s ,ll e, ll l , ll r)
{
if(s>r || e<l)
return 0;
if(s>=l && e<=r)
return st[v];
ll mid=(s+e)/2;
return query(2*v,s,mid,l,r)+query(2*v+1,mid+1,e,l,r);
}
int main()
{
int t;
ll n;
cin>>t;
while(t--)
{
scanf("\n");
cin>>n;
ll mx=-1;
for(ll i=0;i<n;i++)
{
cin>>arr[i];
mx=max(mx,arr[i]);
}
mx=pow(10,7)+1;
build(1,1,mx);
update(1,1,mx,arr[0]);
ll ans=0;
for(ll i=1;i<n;i++)
{
ans+=query(1,1,mx,arr[i]+1,mx);
update(1,1,mx,arr[i]);
}
cout<<ans<<"\n";
}
}
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.