Duongcvp's blog

An update and query range problem
By Duongcvp, 5 years ago, In English

Give an array size N (N<=10^5). There are Q(Q<=10^5) queries and 2 types of queries: (0 l r): Increase a[l], a[l],..., a[r] by 1, and (1 l r): Calculate (a[l]*a[l+1]*...*a[r])%(10^6+3).
Can someone help me solve this problem? Thanks.
And sorry because of my poor English.

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

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What’s the problem source?

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

    I found it in a document, and it was written in Vietnamese.

    → Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it -8 Vote: I do not like it

deleted.

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

    I think you can't modify the array fast because you must update the polynomial after the modify operation. Maybe you should split the array into some blocks instead of use segment tree.

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

      I'm not modifying the array at all. I'm just keeping lazy[] array to know how much I need to add, to given range. Also, I'm not modifying polynomial, rather computing all the queries for given segment of segment tree in the end together at once.

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

        For example,if $$$n = 4$$$ and you should increase $$$a_1,a_2$$$ by $$$1$$$, then I ask the $$$a_1 \times a_2 \times a_3 \times a_4$$$.How can you get the answer? You can't get the answer from the polynomial $$$(a_1 + x) \times (a_2 + x) \times (a_3 + x) \times (a_4+x)$$$ because $$$a_1,a_2$$$ is changed and $$$a_3,a_4$$$ is not changed. you can only get answer by polynomial $$$(a_1 + 1 + x) \times (a_2 + 1 + x) \times (a_3 + x) \times (a_4+x)$$$

        Maybe it is hard to understand,I am sorry for my poor English

        → Reply