EasyCoding's blog

Need help...
By EasyCoding, 10 years ago, In English

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!

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

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

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

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

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

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

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

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

    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.

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

      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 :)

      → Reply