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
Sparse Table implementation
question is simple, doesn't require any data structure except array.O(m*n) is not bad
0.04 with union find and cstdio (was 0.10 using iostream--IO seems like it matters more than algorithm)Last edit: 2018-10-06 18:55:04
to solve anyone can learn these topics.
AC 0.01s using sparse table :D
just like water.. range minimum query simply.. :3
using sqrt decomposition but still run time error.
1. Sparse Table = 0.09 secs...
Last edit: 2018-02-26 22:26:46