GSS7 on SpOJ query

Revision en1, by color_me_red, 2017-06-23 00:15:34

Here is a link to the problem.

Briefly, there is a tree with some values on each node. For each query a,b, I have to find the contiguous subarray with maximum sum in the path a — b. There are range updates a b v, which change the value of the nodes in a — b to some v.

My approach is to decompose the tree (heavy light) and then find the answer(I'll come to what I mean by this) for a -> lca(a,b), and then the same for b -> lca(a,b).

If the path from a -> lca(a,b) passes through five chains, I get all the answers for each chain in the range that belongs to the path a -> lca(a,b). The answer consists of max sum, max prefix sum, max postfix sum, total sum. I store these in a list. And do the same for b -> lca(a,b). I concatenate the two lists appropriately. Then on this final list, I calculate the final answer (exactly same as what's been done for the segment trees of the chains).

Is there a better way that doesn't involve joining all the answers of the involved chains and then finding the answer from them? I'll explain more if I needed.

Tags spoj

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English color_me_red 2017-06-23 00:15:34 1133 Initial revision (published)