1075: 有序数组查询
内存限制：256 MB
时间限制：1 S
评测方式：文本比较
命题人：外部导入
提交：36
解决：22
题目描述
A=[A0,A1,A2,⋯,An] 是一个由 n+1 个 [0,N) 范围内整数组成的序列，满足 0=A0<A1<A2<⋯<An<N。（这个定义中蕴含了 n 一定小于 N。）
基于序列 A，对于 [0,N) 范围内任意的整数 x，查询 f(x) 定义为：序列 A 中小于等于 x 的整数里最大的数的下标。具体来说有以下两种情况：
1. 存在下标 0≤i<n 满足 Ai≤x<Ai+1
此时序列 A 中从 A0 到 Ai 均小于等于 x，其中最大的数为 Ai，其下标为 i，故 f(x)=i。
2. An≤x
此时序列 A 中所有的数都小于等于 x，其中最大的数为 An，故 f(x)=n。
令 sum(A) 表示 f(0) 到 f(N−1) 的总和，即：
对于给定的序列 A，试计算 sum(A)。
基于序列 A，对于 [0,N) 范围内任意的整数 x，查询 f(x) 定义为：序列 A 中小于等于 x 的整数里最大的数的下标。具体来说有以下两种情况：
1. 存在下标 0≤i<n 满足 Ai≤x<Ai+1
此时序列 A 中从 A0 到 Ai 均小于等于 x，其中最大的数为 Ai，其下标为 i，故 f(x)=i。
2. An≤x
此时序列 A 中所有的数都小于等于 x，其中最大的数为 An，故 f(x)=n。
令 sum(A) 表示 f(0) 到 f(N−1) 的总和，即：
对于给定的序列 A，试计算 sum(A)。
输入
从标准输入读入数据。
输入的第一行包含空格分隔的两个正整数 n 和 N。
输入的第二行包含 n 个用空格分隔的整数 A1,A2,⋯,An。
注意 A0 固定为 0，因此输入数据中不包括 A0。
输出
输出到标准输出。
仅输出一个整数，表示 sum(A) 的值。
样例输入 复制
3 10
2 5 8样例输出 复制
15提示
A = [0, 2, 5, 8]
f(0) = f(1) = 0
f(2) = f(3) = f(4) = 1
f(5) = f(6) = f(7) = 2
f(8) = f(9) = 3
sum(A) = f(0) ∗ 2 + f(2) ∗ 3 + f(5) ∗ 3 + f(8) ∗ 2 = 15
f(0) = f(1) = 0
f(2) = f(3) = f(4) = 1
f(5) = f(6) = f(7) = 2
f(8) = f(9) = 3
sum(A) = f(0) ∗ 2 + f(2) ∗ 3 + f(5) ∗ 3 + f(8) ∗ 2 = 15