This problem is about counting the number of triplets such that a[i]>a[j]>a[k] & i<j<k

How can we solve this using Segment tree ? Please help me ?

https://codeforces.com/contest/61/problem/E

Thanks in advance

This problem is about counting the number of triplets such that a[i]>a[j]>a[k] & i<j<k

How can we solve this using Segment tree ? Please help me ?

https://codeforces.com/contest/61/problem/E

Thanks in advance

An immediate idea I can think of is based on 2 segment trees/doable using BIT though.

Make a vector of pairs (a[i],i). Sort it.

I’m basically introducing values in increasing order and counting the number of smaller values with lower index using bit. Thats the basic idea, but this sorting hint should be a good start.

3 Likes

Yeah , i’ve got this . Thanks by the way