Minimize a product
Problem
You are given an array \(A\) of \(N\) integers.
Also, you are given \(Q\) queries of the following type:
- \(1 \ x \ v\): Change the value of the element at \(x^{th}\) index to \(v\) i.e. set \(A[x] = v\).
- \(2 \ l \ r\): Determine the number of pairs \((i,j)\) such that:
- \(l \le i < j \le r\)
- \(A[i] \times A[j]\)is minimum possible among all such possible pairs of elements
Your task is to determine the sum of answers for queries of Type \(2\) over all \(Q\) queries.
Note
- Assume \(1\)-based indexing.
- The sum can be very large, print the output in modulo \(10^9 + 7\).
Input format
- The first line contains an integer \(T\) that denotes the number of test cases.
- For each test case:
- The first line contains two space-separated integers that denotes \(N \ Q\).
- The next line contains \(N\) space-separated integers that denotes the array \(A\).
- The next \(Q\) lines contain queries.
Output format
For each test case, print an integer denoting the sum of the answer for all the queries of Type \(2\) in a new line.
Constraints
\(1 \le T \le 10 \\ 1 \le N, Q \le 10^5 \\ 1 \le l < r \le N \\ 1 \le x \le N \\ 1 \le v, A[i] \le 10^6\)
Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation
For Query 1:
- Pair \((2,3)\) satisfy the required condition as \(A[2] \times A[3] = 6\) is the minimum possible product that can be achieved.
After Query 2:
- \(A[4] = 3\)
For Query 3:
- Pair \((3,4), (4,5), (3,5)\) satisfy the required condition as \(A[3] \times A[4] = A[3] \times A[5] = A[4] \times A[5] = 9\) is the minimum possible product that can be achieved.
Hence, the required answer is 1 + 3 = 4.
