PROBLEM LINKS:
Setter : Shubham Grover##
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Math,Segment Trees,Lazy Propagation
EXPLANATION:
There are 2 types of queries and seeing the constraints we have to process them faster.
Now,we can use segment trees to answer the queries.We can determine the number of zeroes
at the end of a number if we know number of #twos and #fives in its prime factorization.
Number of zeroes=Min(#twos,#fives).
Number of zeroes in product=Min(sum of #twos in elements in product,sum of #fives in elements in product).
Be careful of element having value 0 in product as number of zeroes will be 1.
Since any array element can have value 0 at any point of time we store 3 values at a node
in segment tree sum of number of twos in prime factorization of all the elements in range,
sum of number of twos in prime factorization of all the elements in range and number of
elements in range with value 0.
Now, using lazy propagation we can answer queries in O(log2(Max A[i])+logN) time;
Total Complexity :O(Nlog2(Max A[i])+Q(log2(Max A[i])+logN))
O(log2(Max A[i])) is for calculating number of twos and fives in prime factorization of number.
SETTER’S SOLUTION:
Can be found here