fpvyzv600's blog

Segment Tree problem
By fpvyzv600, 10 years ago, In English

Hi everyone, I'm trying to solve 316E3 - Задание на лето. Despite reading the tutorial link, I could't understand clearly the solution. Could you explain me more detail??

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        wow, I've got it. Thanks you very much :)

        → Reply