#P2021121. 序列查询

序列查询

序列查询

题目描述

题目背景

西西艾弗岛的购物中心里店铺林立,商品琳琅满目。为了帮助游客根据自己的预算快速选择心仪的商品,IT 部门决定研发一套商品检索系统,支持对任意给定的预算x,查询在该预算范围内(≤x)价格最高的商品。如果没有商品符合该预算要求,便向游客推荐可以免费领取的西西艾弗岛定制纪念品。

假设购物中心里有n件商品,价格从低到高依次为A1,A2⋯An,则根据预算x检索商品的过程可以抽象为如下序列查询问题。

题目描述

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的整数里最大的数的下标。具体来说有以下两种情况:

存在下标0≤i<n满足Ai≤x<Ai+1

此时序列A中从A0到Ai均小于等于x,其中最大的数为Ai,其下标为i,故f(x)=i。

An≤x

此时序列A中所有的数都小于等于x,其中最大的数为An,故f(x)=n。

令sum(A)表示f(0)到f(N−1)的总和,即: sum(A)=∑i=0N−1f(i)=f(0)+f(1)+f(2)+⋯+f(N−1)

对于给定的序列A,试计算sum(A)。

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数n和N。

输入的第二行包含n个用空格分隔的整数A1,A2,⋯,An。

注意A0固定为0,因此输入数据中不包括A0。

输出格式

输出到标准输出。

仅输出一个整数,表示sum(A)的值。

数据范围

(原站未提供,导入后需人工补齐)

样例

3 10
2 5 8
15
9 10
1 2 3 4 5 6 7 8 9
45

提示

样例1解释

A=[0,2,5,8]

i0123456789

f(i)0011122233

如上表所示,sum(A)=f(0)+f(1)+⋯+f(9)=15。

考虑到f(0)=f(1)、f(2)=f(3)=f(4)、f(5)=f(6)=f(7)以及f(8)=f(9),亦可通过如下算式计算sum(A): sum(A)=f(0)×2+f(2)×3+f(5)×3+f(8)×2

子任务

50%的测试数据满足1≤n≤200且n<N≤1000;

全部的测试数据满足1≤n≤200且n<N≤107。

提示

若存在区间[i,j)满足f(i)=f(i+1)=⋯=f(j−1),使用乘法运算f(i)×(j−i)代替将f(i)到f(j−1)逐个相加,或可大幅提高算法效率。