given two arrays, of which one is increasing (not necessary strictly) and other is decreasing(strictly actually it is the index of that element from back)and we have to answer q queries [x, y] in which we have to find the maximum value of the product of the value at same indices in array excluding the given range [x, y].
for some given query range [x, y] the array a2 is given by :
= n - i + 1 (if i > y)
= (n - i + 1) - (y - x + 1) (if i < x)
a1 : 1 2 2 3 4 (fixed increasing array)
a2 : 4 - 3 2 1 (for range [2, 2]) : answer is 6 (3* 2 or 2*3)
a2 : 2 - - - 1 (for range [2, 4]) : answer is 4 (4*1)
I thought of applying binary search but as the first array is not strictly increasing it fails!
And how do we construct the second array?I couldn’t understand this “other is decreasing(strictly actually it is the index of that element from back)”,i mean in a bruteforce manner do we have to first construct the second array and then answer queries?If yes how can we construct it in brute force manner?And also u said its decreasing,however in ur eg a2 it doesnt seem so
first we have to construct the 2nd array according to each query(it is the index of that element if taken from back in the new range (i.e. after removing elements in the given range) and then answer query! It can be done easily by brute force but it can have a better solution.
And for the second example please ignore zeroes(as those elements are not considered in this query)
i am thinking of the same but forget offline queries. Thanks a lot! Btw does using offline queries help here? Because we need to remove the lines from the set and it may happen that after adding this line some line may get deleted from set. So, how to overcome that?