题目 30001

静态区间最小值

查看题解 ↗GitHub ↗如何评测
题号
30001
时间限制
10000 ms
内存限制
1024 MB
标签
数据结构倍增
来源
Library Checker (yosupo06) - staticrmq

【题目描述】

给定一个长度为 NN 的整数序列 a0,a1,...,aN−1a_0, a_1, ..., a_{N-1}。

依次处理以下 QQ 个查询:

  • $l_i$ $r_i$:输出 min⁡(ali,ali+1,...,ari−1)\min(a_{l_i}, a_{l_i + 1}, ..., a_{r_i - 1})。

【输入】

第一行包含两个整数 NN 和 QQ,表示序列长度与查询个数。

第二行包含 NN 个整数 a0 a1 ... aN−1a_0\ a_1\ ...\ a_{N-1}。

接下来 QQ 行,第 ii 行包含两个整数 li ril_i\ r_i,表示第 ii 个查询。

文本
$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)\min(a_{l_i}, a_{l_i + 1}, ..., a_{r_i - 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≤5000001 \leq N, Q \leq 500000
  • 0≤ai≤1090 \leq a_i \leq 10^9
  • 0≤li<ri≤N0 \leq l_i < r_i \leq N

【来源】

Library Checker(yosupo06) staticrmq

数据下载

题目 30001 的公开数据

正在读取文件列表…

常用命令

题目 30001 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。