#4740. 区间最小值(第15届-202308)

区间最小值(第15届-202308)

Background

区间最小值

题目描述:

给定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≤10 5),分别表示整数的数量及查询次数

第二行输入n个整数(0≤整数≤105)

接下来m行,每行输入2个整数ai和bi(1≤ai≤bi≤n),分别表示查询的起始位置和终止位置

输出描述:

输出共m行,每行输出一个整数,分别表示每次查询得到的第ai个数到第bi个数之间(包含ai和bi)的最小值

样例输入:

8 3

40 20 10 30 70 50 80 60

3 7

1 2

5 8

样例输出:

10

20

50

Limitation

1s, 1024KiB for each test case.