### atlasworld's blog

By atlasworld, history, 8 months ago, , in problem 459d we have to find the i,j pairs for which f(1,i,a[i]) > f(j,n,a[j]])

we will first count left[i] i.e frequency of a[i] in the range [1,i] and r[i] i.e freq. of a[i] from [i,n] .

after that what to do .. how to solve it in O(n) time ..

please help ! Comments (2)
 » I dont't think that problem can be solved in o(n) time , however here is an o(nlog(n)) time solution using segment tree or any range query data structure ...So all you need in this problem is to precount the function f for each index i, f(1,i,a[i]) and f(i,n,a[i]) and store these values in different arrays , a prefix array let's name it L and a suffix array let's name it R .Now we use segment tree , build it with the suffix array R for each node you store a vector and you only have to merge nodes using a function called merge, you can see an example about it here , now in order to count your answer you only have to answer queries for each index i in [1,n] : how many values in range(i+1,n) that are less than L[i] and add it to the answer , here use lower_bound for each node covering a partial range in (i+1,n) . That's it , i hope that was clear ..
•  » » Thanks AmEr , solved it with slight modification of segment tree .. we can do a range sum query on segment tree while iterating in backwards direction .. link