Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

atlasworld's blog

By atlasworld, history, 18 months ago, In English,

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 !

  • Vote: I like it
  • -8
  • Vote: I do not like it

18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ..

  • »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ..