【题目描述】
给定一个长度为 N 的整数序列 a0,a1,...,aN−1。
依次处理以下 Q 个查询:
$l_i$ $r_i$:输出 min(ali,ali+1,...,ari−1)。
【输入】
第一行包含两个整数 N 和 Q,表示序列长度与查询个数。
第二行包含 N 个整数 a0 a1 ... aN−1。
接下来 Q 行,第 i 行包含两个整数 li ri,表示第 i 个查询。
文本
$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$l_1$ $r_1$
$l_2$ $r_2$
:
$l_Q$ $r_Q$
【输出】
对每个查询输出一行一个整数,表示 min(ali,ali+1,...,ari−1)。
【输入样例】
文本
4 10
2 10 1 100
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
【输出样例】
文本
2
2
1
1
10
1
1
1
1
100
【数据范围】
- 1≤N,Q≤500000
- 0≤ai≤109
- 0≤li<ri≤N
【来源】
Library Checker(yosupo06) staticrmq