Given an array arr[] of size n. Three elements arr[i], arr[j] and arr[k] form an inversion of size 3 if a[i] > a[j] >a[k] and i < j < k. Find total number of inversions of size 3
Examples :
Input : {8, 4, 2, 1}
Output : 4
The four inversions are (8, 4, 2), (8, 4, 1), (4, 2, 1) and (8, 2, 1).
Input : {9, 6, 4, 5, 8}
Output : 2
The two inversions are {9, 6, 4} and {9, 6, 5}
The steps involved are:
1) Firstly data compression with help of map(STL container) or we can also do data compression by storing in another temp array and than replacing the original array with compressed values
2) then counting larger elements than a[i] having index smaller than i with help of ST
3) than counting smaller elements than a[i] having greater index than i with help of ST
We can reduces the complexity of this problem to O(n*log(n)) by Segment tree

Segment Tree with point update & range query
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int smaller[100001]= {0}, larger[100001]= {0};
int dp[400001]= {0};
// std ST insertion operation
// it will increase count of i into ST
void insert(int st, int ss, int se, int i)
{
if(ss == se)
{
dp[st] ++;
return ;
}
int mid = (ss + se) / 2;
if (i<= mid)
insert(2*st, ss, mid, i);
else
insert(2*st + 1, mid + 1, se, i);
dp[st] = dp[2*st] + dp[2*st + 1];
}
// std ST query operation
// return count of elements in range [i, j]
int query(int st, int ss, int se, int i, int j)
{
if (se<ss || ss>j || se<i)
return 0;
if(ss>= i&&se<= j)
return dp[st];
int mid = (ss + se)/2;
int xx = query(2*st, ss, mid, i, j)+query(2*st + 1, mid + 1, se, i, j);
return xx;
}
int countInversion(int a[], int n)
{
int i;
// map is used for data compression
// by data compression we mean that if our input array is [8, 4, 2, 1] then we only have to compare values
// i.e. a[i] > a[j] > a[k] for i < j < k. We don't have to care about what is difference between a[i] & a[j]
// so by using map we convert [8, 4, 2, 1] into [3, 2, 1, 0].
// [3, 5, 2, 7, 3] --> [1, 2, 0, 3, 1]
map<int, int> mp;
for(i = 0; i<n; i++)
{
mp[a[i]]++;
}
map<int, int>::iterator it;
i = 0;
it = mp.begin();
while(it != mp.end())
{
it->second = i;
i ++;
it ++;
}
for(i = 0 ; i < n ; i ++)
{
a[i]= mp[a[i]];
}
// larger[i] contains number of elements larger than a[i] and their index less than i
for(i = 0; i<n; i++)
{
larger[i] = query(1, 0, n-1, a[i]+1, n);
// in query we are calculating larger number than a[i] i.e. between a[i]+1 and n(n-1 is largest number
// that we confirmed by map) and having index smaller than i
// when i = x some intermediate step in for loop only 0 to x-1 index elements are inserted till now
// so there is no case of larger value that any a[i] in segment tree(ST) having greater index than i
insert(1, 0, n-1, a[i]);
// here we are inserting a[i] into ST
}
for(i = 0; i<4*n; i++)
dp[i]= 0;
// smaller[i] contains number of elements smaller than a[i] and their index greater than i
for(i = n-1; i>= 0; i--)
{
smaller[i] = query(1, 0, n, 0, a[i]-1);
// in query we are calculating smaller number than a[i] i.e. between 0 and a[i]-1 as 0 is smallest
// number in array
// when i = x some intermediate step in for loop only x + 1 to n-1 index elements are inserted till now
// so there is no case of smaller value that any a[i] in segment tree(ST) having greater index than i
insert(1, 0, n, a[i]);
// here we are inserting a[i] into ST
}
ll ans = 0;
for(i = 0; i<n; i++)
{
// for an index i larger[i] contains count of number having value greater than a[i] & index less than i
// for an index i smaller[i] contains count of number having value smaller than a[i] & index greater than i
// so if i index element is middle element than larger[i]*smaller[i] number of ways possible with i as
// middle element in inversion
ans += larger[i]*smaller[i];
}
return ans;
}
int main()
{
int a[] = {8, 4, 2, 1};
int n = sizeof(a)/sizeof(a[0]);
cout << "Inversion Count : " << countInversion(a, n);
return 0;
}
Output :
Inversion Count : 4
Time Complexity : O(n*log(n))
Space Complexity : O(n)