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.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Very Hard Queries on Interview Code Editor
Sign Up
to access hints and editorial solutions for Very Hard Queries

Discussion


Loading...
Click here to start solving coding interview questions