Redirecting to
NADOS

Square Root Decomposition

You are given a list of N numbers and Q queries.Each query is specified by two numbers i and j.The answer to
each query is the minimum number between the range between i and j(including i and j).The query are specified using 0 based indexing.

Expected complexity : O(Q * logN)
Input Format
The first line contains N. The next line holds N numbers. Following the list is a number Q. The next Q lines each contain two numbers i and j which specify a query you must answer.
Output Format
For each query, output the Minimum in the range in a line.
Question Video
Constraints
1<= N <= 10^6
1 <= Q <= 10^5
0 <= i,j <= N-1
Sample Input
4
2 4 3 1
4
1 2
1 3
2 2
0 1
Sample Output
3
1
3
2


  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name