I was doing TRIPINV. The problem requires us to find triplets with `ai > aj > ak for i < j < k`

.

I was thinking of using 2 BITs for the same, and use a (Sum) **C** (2), and of sum of (SameElements) **C** (2). But I can't maintain the order of elements this way. For instance, in A[1..6] = 3 2 1 3 2 1 My program would identify A[2],A[5],A[6] as a triplet too.

Can anyone help me out?

PS: **C** denotes Combination

I think that we simply need to calculate for every index

j, how many indicesi<jsatisfy inequalitya_{i}>a_{j}(lets denote result asA), how many indicesk>jsatisfy inequalitya_{j}>a_{k}(lets denote result asB), and add to answerA·B. We can calculateA, adding numbers to BIT in decreasing order, and for calculatingBwe add numbers to another BIT in increasing order.Building the 2nd BIT in the reverse order was very clever. Thank you!

Let's use 2 BITs. First BIT

T1[x] will count number of elements greater or equal thanx, while second BITT2[x] will count number of inversionsi,j(i<jandA[i] >A[j]) such thatA[j] > =x, that is number of inversions with second element greater or equal tox. Then after reading a numbern, we query the first bit forn+ 1 and perform increase operation to the second BIT atnwith that value. Finally we query second BIT forn+ 1 and add that value to our final answer.Code is very short and pretty -> C++ Code

There is a similar problem on CF:

http://codeforces.com/problemset/problem/61/E

Yet another similar problem.