### Duongcvp's blog

By Duongcvp, 10 months ago, ,

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

 » 10 months ago, # |   +8 What’s the problem source?
•  » » 10 months ago, # ^ |   0 I found it in a document, and it was written in Vietnamese.
 » 10 months ago, # | ← Rev. 5 →   -8 deleted.
•  » » 10 months ago, # ^ |   +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.
•  » » » 10 months ago, # ^ |   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.
•  » » » » 10 months ago, # ^ |   +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