RMQSQ - Range Minimum Query
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 [i, j] (inclusive).
Note: the query ranges are specified using 0-based indexing.
Input
The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number Q (Q <= 10,000). The next Q lines each contain two numbers i and j which specify a query you must answer (0 <= i, j <= N-1).
Output
For each query, output the answer to that query on its own line in the order the queries were made.
Example
Input: 3
1 4 1
2
1 1
1 2 Output: 4
1
hide comments
deerawat:
2020-07-30 12:26:14
First question with segment trees!! |
|
syed_tanveer:
2020-07-27 18:47:48
AC 0.04s , segment tree. |
|
i_spidey:
2020-07-23 20:45:15
Done at the first time using segment tree
|
|
scolar_fuad:
2020-06-06 20:04:27
solve first if you have learnt RMQ algorithm |
|
flashadarsh:
2020-05-23 12:48:18
Easy using sqrt decomposition :) |
|
raghav_sharma:
2020-05-15 17:05:49
i am using sparse table in python but it is giving tle. Can someone please tell why? |
|
angshuman_03:
2020-04-23 17:50:58
AC using sparse table!
|
|
medhruv7:
2020-04-03 00:05:03
AC one go , sparse table |
|
shanto09:
2020-03-11 14:50:53
AC with sparse table.. |
|
chaudhary_19:
2019-09-09 21:49:30
Sparse Table makes your life easier !!! |
Added by: | Joshua Kirstein |
Date: | 2014-10-18 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |