Vasiljko's blog

Adding geometric sequence to the segment
By Vasiljko, history, 4 years ago, In English

I was solving 446C - DZY любит числа Фибоначчи today where it's needed to add geometric sequence to the segment but the ratio is always the same. So I was wondering how to solve the problem where we are given queries of type $$$L,R,A,B$$$ and we need to add geometric sequence $$$A,AB,AB^2,AB^3,... AB^{R-L}$$$ to the segment $$$[L,R]$$$? There is also a sum query for some range.

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Does $$$O(n^{5/3} \log C)$$$ offline count xd

    E: nvm, I don't even know how to do that.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

Edit: I just wrote a bunch of text though but it is incorrect :/ my bad.

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

Just hold lazy vector of all your updates(ratio, range starting value) while also holding sum of lazy updates in lazy int, then when you need to push move all updates in vectors to child vectors while adding to childs lazy sums using formula for geo series, delete from current vector, and add lazy sum to main sum.

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

    How do you merge the lazy updates of two different series with different ratios?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      That's why you hold the updates in vectors on each node, and just hold the series sum in a lazy variable. That way you hardly have to think about merging them besides adding the updates to the lazy or sum variable. Fairly sure it is still amortized logn, but don't actually no time complexity, but I've used this trick multiple times.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Not sure I understand. If you make $$$N$$$ add queries of the form $$$1 \, N \, 1 \, B$$$ for different values of $$$B$$$ and then a query of "sum from $$$i$$$ to $$$i$$$" for every $$$i$$$ in $$$1 \ldots N$$$, how is it not $$$\Omega(N^2)$$$?

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

          Hmm I think you're right actually rip. I guess I was just lucky it works for sparse data, but just to show I'm not making up I used it here's an example I actually used this and it somehow worked: link.

          → Reply