### kgargdun's blog

By kgargdun, history, 3 days ago,

Hi, I am on my adventure to solve CSES problem set. I found this nice editorial for Range Query section here

But i guess some new problems were added or were skipped there. I am struggling in one such problem. here Any hint/approach will be highly appreciated!

EDIT: Yay AC ! I tried to code it as simple as possible.

AC solution

• +1

 » 3 days ago, # |   +3 The main challenge with the problem is finding $cost(i) = \min\limits_{1 \leq j \leq n}(p_j + |i-j|)$ quicklyWe can split the cost into two parts: $cost(i) = \min(p_j + (i - j))$ when $j \leq i$ and $cost(i) = \min(p_j + (j - i))$ when $j \geq i$Combining them together, we get $cost(i) = \min(\min\limits_{1 \leq j \leq i} (p_j - j) + i, \min\limits_{i \leq j \leq n}(p_j + j) - i)$We can use two point-update, range-minimum-query segment trees to achieve this. One stores $p_i - i$ and the other stores $p_i + i$.
•  » » 3 days ago, # ^ |   0 thanks!
 » 3 days ago, # |   0 Auto comment: topic has been updated by kgargdun (previous revision, new revision, compare).