We are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Consider the following recurrence relation:
We are interested in calculating $$$f(n)$$$. Is there a way to calculate it with the time complexity being better than $$$\mathcal{O}(n^2)$$$?
UPD: I forgot to mention that the array $$$b$$$ is increasing (i.e. $$$b[i] \leq b[i+1]$$$). Don't know if that helps though...
If I understood the task conditions correctly, you can use a segment tree and a maxque. Calculate in process a and replace in the tree of segments the number that will be added to f(i). Of all of them, find the minimum and count further
The final asymptotics of O(n log n)
I'm not sure I understand your approach. Could you elaborate, please?
going from left to right through the array, we will count f(i) for each i. Next, we will use a stack with a maximum. In short, it will store the positions of all local maxima starting from the beginning (more details in the picture).
I.e. we store the positions in which the maximum will change. next, when we add another number to our stack, the following happens: We remove from the stack all numbers that are smaller than ours. If we do this, it is obvious that now the maximum from the number j to our i is the nearest element to the right or equal to us, which lies in the stack. Now we can imagine that each element from the stack is actually a segment on which this element will be the maximum. Now we just have to make a tree of segments with adding on the segment and searching for the maximum on the segment, simultaneously deleting and changing the segments in the stack and everything is ready.
Are you saying that to calculate $$$f(i)$$$ we should consider only those values of $$$j$$$ that are between the index of the previous element greater than $$$a[i]$$$ and $$$i-1$$$?
let met explain it a little bit better.
we find the values of $$$f$$$ from left to right. to do that, we maintain a range add-range min segment tree $$$seg$$$, such that when we are calculating $$$f_i$$$, $$$seg_j$$$ is equal to $$$f_j + max(a_{j+1} , \cdots , a_i)$$$. then, we just make a query for segment $$$[b_i , i)$$$ to find the value of $$$f_i$$$.
let $$$g_i$$$ be the rightmost $$$j < i$$$ such that $$$a_j > a_i$$$ (or 0 if it doesn't exist.) we know how to calculate $$$g$$$ using a stack. now, we know that $$$seg_j = f_j + max(a_{j+1},\cdots,a_{i-1})$$$, and we want to update it such that $$$seg_j = f_j + max(a_{j+1},\cdots,a_i)$$$. it's easy to see the values of $$$seg_j (j \leq g_i)$$$ won't change.
let's look at indexes $$$g_i < j < i$$$:
- for $$$g_{i-1} < j \leq i-1$$$, $$$seg_j = f_j + a_{i-1}$$$, but it should be $$$f_j + a_i$$$
- for $$$g_{g_{i-1}} < j \leq g_{i-1}$$$, $$$seg_j = f_j + a_{g_{i-1}}$$$, but it should be $$$f_j + a_i$$$
- for $$$g_{g_{g_{i-1}}} < j \leq g_{g_i}$$$, $$$seg_j = f_j + a_{g_{g_{i-1}}}$$$, but it should be $$$f_j + a_i$$$
- and so on.
as we can see, the segment $$$[g_i+1 , i)$$$ is divided into several subsegments, such that we need to add the same number to all values in the same subsegment to update values of our segment tree.finally, we should set $$$seg_i$$$ to $$$f_i$$$. here is a pseudo code:
hope it helps!
But isn't the complexity $$$O(n^2)$$$ in the worst case?
no, because if we add something to $$$(g_j , j]$$$ for some $$$j$$$, we will never add something else to a segment ending at $$$j$$$, and this results in at most $$$O(n)$$$ additions and total complexity will be $$$O(nlogn)$$$.
actually, complexity analysis is the same with complexity analysis of finding values of $$$g$$$, each "set $$$seg_i$$$ to $$$f_i$$$" corresponds to a push operation on stack and each "jump from $$$j$$$ to $$$g_j$$$" corresponds to a pop operation on stack.
Auto comment: topic has been updated by suzie_q (previous revision, new revision, compare).
Is b strictly increasing or non-decreasing? I think the former condition makes the problem a lot easier.
It's just non-decreasing.
1d1d?
i think that we can use it here
Isn't the fact that we want the minimum over all $$$j$$$ such that $$$b[i] \leq j < i$$$ going to ruin this approach?
I think that will help us. Because for 1D1D (i might be wrong) we need to $$$opt[i] <= opt[i + 1]$$$ everytime, so that only helps us, because $$$b[i] <= b[i + 1]$$$