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

Segment Tree problem
Автор fpvyzv600, 10 лет назад, По-английски

Hi everyone, I'm trying to solve 316E3 - Summer Homework. Despite reading the tutorial link, I could't understand clearly the solution. Could you explain me more detail??

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

The key is the merging step

While merging and , we need to shift the Fibonacci multiplier of the second one by (l2 - r1) to the right , so that we get

Shifting can be done by using identity Fn + m = FnFm - 1 + Fn + 1Fm

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    F[n+m+1] = F[n]*F[m-1] + F[n+1]*F[m] ??

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Yes. Proof can be found from matrix exponentiation, or by induction here

      Then make 2 segtree, for maintain (supposed to be seg1) and (supposed to be seg2).

      Sorry if this explanation seems unclear. More detail you can check my submission 7338693

      → Ответить