Блог пользователя kgargdun

Автор kgargdun, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The main challenge with the problem is finding $$$cost(i) = \min\limits_{1 \leq j \leq n}(p_j + |i-j|)$$$ quickly

We 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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by kgargdun (previous revision, new revision, compare).

»
3 года назад, # |
  Проголосовать: нравится +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);