Problem : Mina gives an integer V with length N to John. Then Mina changes V by the following command: “i j d”. This means “Change the digits in V from position i to j to d”, where 0 is the position of the most significant digit of V and N-1 is the position of the least significant digit. After each of these commands, John needs to calculate the sum of digits for U, where U = 2V. For example, let V = 1234. If Mina’s command is “0 2 2”, V becomes 2224. U = 2V = 4448. So sum of digits of U = 4 + 4 + 4 + 8 = 20, which is the answer John should provide. N (N<100001) and Query (Q<50001)
I am trying to solve this problem with segment tree with lazy , but figure out the solution.
How to solve this problem ?
Hi, I will try to explain the solution. Assume we have V = 6699 => N = 4. Our tree will have 4 leaves — one for each digit. Now, in a leaf you need to store only the sum of the digits of 2*d where d is the digit in the leaf. 9*9=18. It doesn't matter if we will add 1 this time or we will transmit it to the left, we will always add just 1 so we will store 1+8=9 in that leaf.
In each node, that is not a leaf node, you should store the sum of its children so it is the standard segment tree problem — change the numbers in the interval [a;b] to c or find the sum of the numbers in the interval [a;b].
How to change the numbers in the interval [a;b] to c ? I know to add the numbers c in the interval [a;b] .
It's the same but you change it instead of adding c. I will provide a code after a moment :)
I have a idea to store 2 segment tree both are doing add the numbers c in the interval [a;b] , one hold the previous and one recent if I subtract then get the value :) But I think there is a easy way to do that , my one is the worst !
Here is the code. Tell me if you have questions :)