Hard Data Structures > Segment Tree/Interval Tree

Software Engineering requires knowledge about algorithms, data structures, design pattern, UML diagram, software development approach. The main focus of all this knowledge is to make the software more efficient, robust and workable. Because if you develop a software which does something slower than human, then what is the point of building that software? Below, there is a problem which can be done with simple looping to all the elements of the array for each query, but that is not efficient, can you make it efficient? Given an array with **N** elements, indexed from **1** to **N**. Now you will be given some queries in the form **I J**, your task is to find the minimum multiplication value of all possible interval between index **I** to **J**, and also for that multiplication value you need to find the longest interval. Lets say we have an array A size 5, indexed from 1 to 5. Now the multiplication value of the interval [1,3] = A[1]*A[2]*A[3] Input: ------ Input starts with an integer **T (≤ 5)**, denoting the number of test cases. The first line of a case is a blank line. The next line contains two integers **N (1 ≤ N ≤ 10^5), q (1 ≤ q ≤ 10^5)**. The next line contains **N** space separated integers forming the array. There integers range in **[0, 10^5]**. The next **q** lines will contain a query which is in the form **I J (1 ≤ I ≤ J ≤ N)**. Output: ------- For each test case, print the case number in a single line. Then for each query you have to print a line containing three numbers, first one is the minimum multiplication value of all possible interval between index **I** to **J**, second and third number will point to the start index and end index of the interval which is longest interval between index **I** to **J** having the minimum multiplication value. If there are multiple intervals having the minimum multiplication value as well as the longest then print the interval which starts earlier. See the output section for further understanding Sample Input ------------ 2 5 3 2 22 10 12 2 2 4 4 5 1 5 2 1 10 10 1 2 Sample Output ------------- Case 1: 10 3 3 2 5 5 2 1 1 Case 2: 10 1 1 **Notes** For the first test case, for query 2, 4, these intervals are possible: [2,2] = 22 [2,3] = 22 * 10 = 220 [2,4] = 22 * 10 * 12 = 2640 [3,3] = 10 [3,4] = 10 * 12 = 120 [4,4] = 12 Among all of these intervals, [3,3] interval have the minimum multiplication value. For the Second test case first query [1,2] we have two longest intervals with minimum multiplication value [1,1], [2,2]. So print [1,1] as it starts earlier.

Ahmad Faiyaz