There is this classical problem of counting number of inversions in an array.
Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A.
This problem can be found here.
I found this problem on CF where we need to find number of such triples
(i,j,k) such that
i<j<k and A[i]>A[j]>A[k].
I solved both of the problems using BIT.
For the second problem, I counted number of numbers greater than A[i] at its left (left[i]) and number of numbers less than A[i] at its right (right[i]). So the output is summation of right[i]*left[i] for all i from 0 to n-1.
Now I have a question, what if the problem is counting inversions of length N? It means we need to find number of such combinations
(i,j,k,...) such that i<j<k<... and A[i]>A[j]>A[k]>...
What should be a generalized solution for this problem?