利普希茨序列

发布时间: 2018年1月29日 10:26   最后更新: 2018年2月11日 23:54   时间限制: 1000ms   内存限制: 128M

对于函数$f:\mathbb{R}→\mathbb{R}$,若$∃K∈\mathbb{R}$($K$为常数),不等式$|f(x)-f(y)|≤K|x-y|$对$∀x,y∈\mathbb{R}$恒成立,称此函数利普希茨连续。今天我们研究这货的离散版本……

对于一个序列$h[1..n]$,我们定义利普希茨常数如下:

如果$n<2$,$L(h)=0$

如果$n≥2$,$L(h)=\max \limits_{1≤i<j≤n}⁡⌈\frac{|h[j]-h[i]|}{|j-i|}⌉$

换句话说,$L=L(h)$是满足对$∀1≤i,j≤n$,$|h[i]-h[j]|≤L|i-j|$恒成立的最小非负整数。

给定你一个长度为$n$的序列$a[1..n]$以及$q$个查询。对于每个查询$[l,r]$,考虑子序列$s=a[l..r]$,试确定$s$的所有连续子序列的利普希茨常数之和

有多组测试数据,(数据组数$≤20$)。对于每组数据,第一行有两个整数$n$和$q$,表示序列$a$的长度以及查询的个数。第二行有$n$个数$a_1,a_2,…,a_n$,中间以空格分割。接下来$q$行每行两个整数$l,r$。
$2≤n≤10^5$
$1≤q≤100$
$0≤a_i≤10^8$
$1≤l < r≤n$

对于每组测试数据,每个查询输出一个整数表示序列$a[l..r]$所有子序列的利普希茨常数之和。每组测试数据间空一行。

复制
10 4
1 5 2 9 1 3 4 2 1 7
2 4
3 8
7 10
1 9
7 6
5 7 7 4 6 6 2
1 2
2 3
2 6
1 7
4 7
3 5
17
82
23
210

2
0
22
59
16
8

本题的输入数据量较大,建议使用高效的读写方式:C++使用scanf/printf代替cin/cout,Java使用BufferedReader/PrintWriter代替Scanner/System.out。

第一个样例的第一个查询:

$L([5,2])=3$

$L([2,9])=7$

$L([5,2,9])=7$

请注意输出格式,没有格式错误。

math data structure

Weekly Training 2018.1.28