Ashish
BAN USERHave a look at this solution by Binary Indexed Tree : -
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define sc(a) scanf("%lld",&a)
#define sc1(a,b) scanf("%lld%lld",&a,&b)
#define sc2(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define pc(a) printf("%lld\n",a)
#define pc1(a) printf("%lld ",a)
const int MOD=1e9+7;
ll n;
void update(ll idx,ll val,ll bit[])
{
for(;idx<=n+1;idx+=(idx&-idx))
bit[idx]+=val;
}
ll query(ll idx,ll bit[])
{
ll ans=0;
for(;idx>0;idx-=(idx & -idx))
ans+=bit[idx];
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
ll ar[n];
vector<pair<ll,ll>> v;
for(ll i=0;i<n;++i)
cin>>ar[i],v.pb({ar[i],i});
sort(v.begin(),v.end());
for(ll i=0;i<n;++i)
{
ar[v[i].second]=i+1;
}
ll bit[n+1];
memset(bit,0,sizeof(bit));
ll ans[n];
for(ll i=n-1;i>=0;i--)
{
ans[i]=query(n,bit)-query(ar[i]-1,bit);
update(ar[i],1,bit);
}
for(ll i=0;i<n;++i)
cout<<ans[i]<<" ";
cout<<endl;
return 0;
}
C++ code implementation : -
- Ashish August 29, 2017