B. A12*【RMQ】区间最大和最小差[USACO07JAN] Balanced Lineup G

传统题

40ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $n$ 个数 $a_i$ 。

有 $q$ 次询问，每次询问给出两个数 $l$ 和 $r$ ，表示询问区间 $[l,r]$ 内最大值和最小值的差。

第一行两个数 $n \ q \ (1\le n\le 5\times 10^4,1\le q\le 1.8\times10^5))$。

下来 $n$ 个数 $a_i\ (1\le a_i\le 10^6)$ 。

下来 $q$ 行，每行两个整数 $l \ r$ 。

输出共 $q$ 行，对于每组询问输出一个整数，表示询问区间内最大值与最小值的差。

6
3
0