Codeforces-problem E doubt

1

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 ?

Thanks in advance :slight_smile:

2

Is that this question in disguise?

3

@ssjgz Yes , its almost same but i am unable to solve it using segment tree .

1 Like
4

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
5

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