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

Need help...
Автор EasyCoding, 9 лет назад, По-английски

Hello everyone!

Can someone tell me how to make update on segment (from l to r)?

If you can write a code, please send me.

Thanks for attention!

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

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

Ex: Now, I want to add w for each elements on segment and I want to get sum on Segment My UpDate Code

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

http://pastie.org/10009594. Sum from l to r and add e from l to r

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

What do you need — only update or update + sum queries? Post the problem statement if it is possible.

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

    Here is statement :

    Given n, and array A(all numbers less than 10^9).

    Then given m, and m requests :

    1) + l r d, add to all numbers from l to r d (1 <= l <= r <= n, 0 <= d <= 10^9).

    2) * l r d, multiply to all numbers from l to r d (1 <= l <= r <= n, 0 <= d <= 10^9).

    3) ? p, print p-th number modulo 10^9 + 7.

    P.S This problem from Republic olympiad in Kazakhstan.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

      Okay, then my idea is a segment tree with two arrays for lazy propagation — lazy_add and lazy_mult.

      If you need the sum for the interval stored in node Node, then you can get it with tree[Node]*lazy_mult[Node]+lazy_add[Node].

      If you need to add t to the interval stored in node Node, then you can just do lazy_add[Node]+=t.

      If you need to multiply by t the interval stored in node Node, then you can just do lazy_add[Node]*=t and then lazy_mult[Node]*=t.

      And you should not forget to get the answer modulo 10^9+7 every time you do these operations :)

      → Ответить