Блог пользователя atlasworld

Автор atlasworld, история, 5 лет назад, По-английски

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 !

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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