Very Hard Queries (Problem From Contest)

[myra404]

I need help in solving the following problem which was asked here - https://www.interviewbit.com/problems/very-hard-queries/.

You are given an array A having n integers.
You have to perform some very hard queries on A.

There are 2 types of queries

1 id X, change A[id] with X.
2 L R, you have to find the minimum
number of steps required to change all elements in [L, R] such that
every element in [L, R] will have the odd number of divisors. In one step you can choose any element from A and can add or subtract 1 from it.
Note that in the second type of query, the array does not change.

Input Format

The 1st argument given is an integer array A.
The 2nd argument given is a 2D integer array B, where B[i] denotes ith query
Output Format

Return an Integer X % (1e9 + 7), the sum of answer for each query of type 2.
Constraints

1 <= N <= 100000
1 <= A[i], X <= 100000
1 <= number of queries <= 100000
1 <= id, L, R <= N
For Example

Input:
A = [1, 2, 3]
B = [[2, 1, 1], [2, 1, 2], [1, 3, 1], [2, 1, 3]]
Output:
2

Explanation:
query 1: we don't need any steps as 1 has an odd number of divisors, so the answer is 0.
query 2: in 1 step we can change 2 to 1, so the answer is 1.
query 3: change value of A[3] with 1, array after the 3rd query is A = [1, 2, 1]
query 4: again in 1 step we can change 2 to 1, so answer is 1.

So the sum of answers to all queries of type 2 is 2.

Can anyone guide me how do I solve this??

[tpb]

What kind of numbers have an odd number of divisors? If you're not sure, try writing out the divisors of the first 16 numbers.