COUNZ - Editorial

counz
editorial
lazypropagation
math
segment-tree
segment-trees

#1

PROBLEM LINKS:

Practice

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*)+logN) time;

Total Complexity :O(Nlog2(Max A*)+Q(log2(Max A*)+logN))
O(log2(Max A*)) is for calculating number of twos and fives in prime factorization of number.

SETTER’S SOLUTION:

Can be found here