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

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

I was solving 446C - DZY Loves Fibonacci Numbers 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.

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

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

Anyone?

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

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

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

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.

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

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

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

      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.

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

        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)$$$?

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

          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.