### dhruvmullick's blog

By dhruvmullick, history, 9 years ago,

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

• +1

| Write comment?
 » 9 years ago, # |   +3 I think that we simply need to calculate for every index j, how many indices i < j satisfy inequality ai > aj (lets denote result as A), how many indices k > j satisfy inequality aj > ak (lets denote result as B), and add to answer A·B. We can calculate A, adding numbers to BIT in decreasing order, and for calculating B we add numbers to another BIT in increasing order.
•  » » 9 years ago, # ^ |   0 Building the 2nd BIT in the reverse order was very clever. Thank you!
 » 9 years ago, # | ← Rev. 2 →   +1 Let's use 2 BITs. First BIT T1[x] will count number of elements greater or equal than x, while second BIT T2[x] will count number of inversions i, j (i < j and A[i] > A[j]) such that A[j] >  = x, that is number of inversions with second element greater or equal to x. Then after reading a number n, we query the first bit for n + 1 and perform increase operation to the second BIT at n with that value. Finally we query second BIT for n + 1 and add that value to our final answer. Code is very short and pretty -> C++ Code
 » 9 years ago, # |   0 There is a similar problem on CF:http://codeforces.com/problemset/problem/61/E
 » 9 years ago, # |   0 Yet another similar problem.