VirtualDimension's blog

By VirtualDimension, history, 6 weeks ago, In English

f(l, r) = max(al,al+1...ar), g(l, r) = min(al, al+1...ar)

How can i calc ∑∑f(l,r) * g(l,r) mod 1e9 + 7?

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Use a stack to find the l & r for each 'i' such that l <= i <= r and f(l, r) = a[i], and store these in an array 'big'. Do the same thing for each 'i' such that g(l, r) = a[i], and store these in an array 'small'. Both of these tasks can be done in O(N).

Let's try to find ∑ g(l, r). This can be done in O(N) by iterating through small and finding the sum of ∑ (a[i] * (small[i].r — small[i].l + 1)). It should be easy to understand why this is the case. Let's call this sum 'sum_g'.

Our answer turns out to be ∑ (a[i] * sum_g * (large[i].r — large[i].l + 1)). Of course, you should be careful with mods when calculating each quantity.