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.
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).
For each query, output the answer to that query on its own line in the order the queries were made.
1 4 1
1 2 Output: 4
how to solve it ussing DSU by youssifgamal ?? too difficulty
how could we solve it using DSU?
+ Sprase table (0,12s, 11M): <snip>
Also possible to solve using disjoint set union (https://cp-algorithms.com/data_structures/disjoint_set_union.html#arpa)
i keep getting WA on test 5 and have no ideas whats wrong
Algo - Segment tree
Yeah exactly Errichto's video on sparse table is excellent. Done with sparse table.
Solved using Square Root Decomposition, Segment tree and Sparse Table.