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

An update and query range problem
Автор Duongcvp, 5 лет назад, По-английски

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.

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

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

What’s the problem source?

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

deleted.

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

    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.

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

      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.

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

        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

        → Ответить