### kgargdun's blog

By kgargdun, history, 5 months 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

• -2

 » 5 months 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$.
•  » » 5 months ago, # ^ |   0 thanks!
 » 5 months ago, # |   0 Auto comment: topic has been updated by kgargdun (previous revision, new revision, compare).
 » 5 months ago, # |   +3 Still, there is a bug  lli left = query(arr, tree2, 0, n-1, **1**, a-1, 1); should be replaced with  lli left = query(arr, tree2, 0, n-1, **0**, a-1, 1); 
•  » » 5 months ago, # ^ | ← Rev. 2 →   +1 Thanks for pointing that out! (fixed)