gi_sha's blog

Help needed in Segment Tree with lazy propagation (updating a range with fibonacci numbers. Div 1. Problem 446 C)
By gi_sha, history, 6 years ago, In English

I was trying this question, but repeatedly getting wrong answer on test case 5. I have tried a lot but cannot find where am I making the mistake.
My approach-
I have used segment trees with lazy propagation.
For each query of type 1, I will update my segment tree nodes with the sum of fibonaci numbers added corresponding to the nodes of the tree.
Then for finding answer to query [L-R], I have to just find the sum of values of the corresponding nodes from the tree and add sum of original array values in [L-R].
I was using the property that if one knows first two fibonacci numbers then one can find n th fibonaci number and also sum of first n fibonacci numbers. code link.
Any help given in this regard will be highly appreciated.
Edit: I am also not able to understand the editorial that how does a2=b2 mod M => a=b mod M. So please help me by sharing your opinions and approaches.

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

Comments Comments (10)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't look at the problem with your code, just want to help with a2 = b2[M] thing.

a2 = b2[M] => a2 - b2 = 0[M] => (a - b)(a + b) = 0[M]. Since M is prime (not composite) (109 + 7), it will perfectly divide either (a - b) or (a + b) (or both). For this problem, I think anyone of them will be okay because we will be using the square of the result so the sign doesn't matter. But in the editorial they took the first one to get a = b[M].

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

    Thanks for considering.
    But I feel that's not true always.
    Let A=a2-b2=0 mod M.
    and B=a-b=0mod M
    and C=a+b=0 mod M
    One knows that A is definitely true but one cannot say for sure that B is also true.
    Though one can reach A assuming B to be true.

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

      It's more like B OR C is true if A is true and M is a prime modulo. See Euclid's lemma.

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

        Yes, exactly.But you cannot consider B to be definitely true(as only C can be true also).

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

          It doesn't matter which one you pick for this problem, the sign will become positive in any case. Look at the comments in the editorial of the problem for more info.

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

            Consider 42=1 mod 5.
            Then according to you I can say 4=1 mod 5. Which is not true but 4=-1 mod 5 is true.

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

              I get your point but it is not what I'm trying to say. I'm talking about this problem specifically, not in general. My first comment explains it clearly I think. Please check this out

              → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

it's useful

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

    Yes I used same idea just maintained segment tree storing first two Fibonacci corresponding to each segment represented by the node.

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

      Then a matrix for each level? (To calculate mid value fast)

      → Reply