#2581. 区间最小值
区间最小值
区间最小值
题目描述
给定n个整数,从1到n顺序编号,接下来进行m次查询,第i次 查询第ai个数到第bi个数(包含ai和bi)之间的最小值并输出。
例如:n=8, 8个正整数依次为: 40 20 10 30 70 50 80 60
m= 3, 3次查询分别为:
a1 =3, b1= 7
a2=1,b2= 2
a3=5,b3= 8 第一次查询:第3个数(10)到第7个数(80)之间最小值是10;
第二次查询:第1个数(40)到第2个数(20)之间最小值是20;
第三次查询:第5个数(70)到第8个数(60)之间最小值是50;
故输出:
10
20
50
输入格式
第一行输入两个整数n和m(1<=n, m<=1000), 分别表示整数的数量及查询次数
第二行输入n个整数(0≤整数<100000)
接下来m行,每行输入2个整数ai和bi(1<=ai <= bi <= n),分别表示查询的起始位置和终止位置
输出格式
输出共m行,每行输出一个整数,分别表示每次查询得到的第ai个数到第bi个数之间(包含ai和bi)的最小值
样例 #1
样例输入 #1
8 3
40 20 10 30 70 50 80 60
3 7
1 2
5 8
样例输出 #1
10
20
50