子数组极差查询
题目描述
小红有一天拿到了 M 个数组 A[x] (1 <= x <= M),他用这个数组构造 M 个新数组 B[x],其中 A[x][i] 代表 B[x] 数组中有 A[x][i] 个 i。例如,若 A[x] = [2,3,1],那么 B[x] = [1,1,2,2,2,3]。
聪明的小红把这些数组用某种神秘的方法压缩成了一个长度为 N 的数组 C,每个 A[x] 都能用 C 的某个子数组表示,因此,对于每个数组 A[x], 小红只会给你 A[x] 在 C 数组出现的左边界 L 和右边界 R。
现在给定 C 数组 和 每个 A[x] 在 C 数组中的左边界与右边界,你需要帮小红对每个 1 <= x <= M 分别求出对应 B[x] 数组中所有连续子数组的极差之和。由于答案可能过大,请对 1000000007 取模。数组的极差指数组中的最大值减去数组中的最小值。
输入描述
第一行有两个正整数 N, M。
第二行有 N 个正整数,表示 C。
后面有 M 行, 每行有两个整数 L, R,按顺序表示 A[x] 在 C 数组出现的左边界和右边界。
输出描述
输出有 M 行, 每行一个整数,第 x 行 表示 B[x] 数组中所有连续子数组的极差之和。
输入示例
3 4
2 1 1
1 2
1 3
1 1
2 3
提示信息
A[1] = [2, 1] 时,B[1] 数组为 [1, 1, 2]。
此时 B[1] 数组共有 6 个连续子数组:
[1] 的极差为 0
[1] 的极差为 0
[2] 的极差为 0
[1, 1] 的极差为 0
[1, 2] 的极差为 1
[1, 1, 2] 的极差为 1
因此答案是0 + 0 + 0 + 0 + 1 + 1 = 2
1 <= N, M <= 100000
1 <= C[i] <= 1000000000
1 <= L <= R <= N