TooMuchPainTheseDays's blog

By TooMuchPainTheseDays, history, 2 years ago, In English

Can someone help me to solve this problem ?
Actually, this problem was in my brain but I didn't find it anywhere. (so I can't provide link)

Problem :


Given array of size N ( N <= 105 )
we have to perform 2 queries.
query of type 1 : 1 l r
increase the value of a[l] by 1 , a[l+1] by 2 , a[i+2] by 3 ,... a[r] by r-l+1
query of type 2 : 2 l r
print the sum of range [l,r]
Thanks in advance.
| Write comment?
»
2 years ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

Take a lazy tag $$$lazy_1$$$ in each node on the segement tree means that increase the value of $$$a_l$$$ by $$$lazy_1$$$ , $$$a_{l+1}$$$ by $$$2*lazy_1,\dots$$$ $$$a_{r}$$$ by $$$(r-l+1)*lazy_1$$$, and a lazy tag $$$lazy_2$$$ means that increase the value of $$$a_{l\dots r}$$$ by $$$lazy_2$$$. And maintain the sum.

When there is a query of type 1 and we'll divide the queried segment into two halves, increase the value of $$$lazy_1$$$ in the left node and right node by $$$1$$$. Then we increase the value of $$$lazy_2$$$ in the right node by $$$L_{rightson}-ql$$$ (here $$$L_{rightson}$$$ means left endpoint of right node,$$$ql$$$ is $$$l$$$ in the query).

When pushing down the lazy tags, you can push down $$$lazy_2$$$ as usual (I believe that you know.), and you should use summation formula of arithmetic sequence to push down $$$lazy_1$$$. concretely, we increase the sum we're pushing by $$$\frac{(lazy_1+lazy_1*(size))*size}{2}$$$ (here $$$size$$$ means the size of node we're pushing).

Forgive me for my poor expression.

the main code...(maybe not right but I think it's right.)