We use a lazy segment tree. This data structure will not be discussed in detail as other resources can be found on this data structure.

For each node, we store a variety of values. bestA and bestB store the best ~A~ and ~B~ values, respectively. best is the best ~A + B~ value.

We do standard lazy segment tree updates and queries. The only important operation to discuss is the lazy propagation.

Let us first consider propagating a lazy set operation (type A). The other operation (type B) is the max operation. We can propagate these in either order.

For propagating an operation of type A, let the number we are setting everything to be ~x~. Note that since all the values are the same, ~bestA = x~. Thus, ~best = x + bestB~. This is the easier operation.

For propagating an operation of type B, let the number we are using be ~x~. Now obviously, ~bestB = \max(bestB, x)~. However, how are we to update ~best~?

We note that the new best has two options. One option is ~bestA + x~. This is quite obvious since each B value is now at least ~x~. The second option is the previous value of ~best~. The second case is if there exists a position ~i~ where ~B_i > x~ and ~A_i + B_i > bestA + x~. The reason is that this operation will not decrease ~best~. Thus, if ~best~ changes, it will be equal to ~bestA + x~, since each B item is at least ~x~. Otherwise, ~best~ stays just as it was before.

Note that the values for ~B_i~ and ~A_i~ can be zero, so you have to store a boolean to keep track of laziness (sorry not sorry).

P.S. This problem was inspired by my attempts at Tourism. I knew of a monotonic solution but it didn't click with me, so I just developed a new data structure instead. When in doubt, bash it with DS!