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
|
shrikant1999:
2022-10-11 10:58:19
<snip>
|
|
trumcspkkk6969:
2022-10-02 12:36:25
how to solve it ussing DSU by youssifgamal ?? too difficulty |
|
youssifgamal:
2022-08-18 03:31:44
how could we solve it using DSU?
|
|
linhthebest:
2022-05-19 13:03:48
+ Sprase table (0,12s, 11M): <snip>
|
|
wlguedes:
2022-05-11 02:48:15
Also possible to solve using disjoint set union (https://cp-algorithms.com/data_structures/disjoint_set_union.html#arpa) |
|
namvinhkhang:
2021-12-27 12:05:26
i keep getting WA on test 5 and have no ideas whats wrong
|
|
mr__abhilash:
2021-10-27 14:35:14
good question |
|
shofiqur_052:
2021-10-17 19:13:09
Algo - Segment tree
|
|
amit2808_:
2021-09-10 08:23:01
Yeah exactly Errichto's video on sparse table is excellent. Done with sparse table. |
|
moarvivek:
2021-07-23 15:05:08
Solved using Square Root Decomposition, Segment tree and Sparse Table. |
Added by: | Joshua Kirstein |
Date: | 2014-10-18 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |