#1747. 爬楼梯
爬楼梯
爬楼梯
题目描述
标题: 爬楼梯 - Problem - QOJ.ac
#5405. 爬楼梯
The problem was used in the following contests:
老 M 是一个知名的混元形意太极大师,经常会有仰慕者前来拜师学艺,但他们必须经过严格的入学考试:爬楼梯。
老 M 的道场有 n 个平台排成一列,第 i 个平台的高度为 hi,从第 i 个平台爬楼梯到第 i+1 个平台所需要消耗的体力为 |hi−hi+1|。
当第 j 个仰慕者来拜师学艺时,老 M 会指定一个区间 [lj,rj],取出这个区间内的所有平台,并使用内功将他们重新排列(不改变原序列),使得爬完所有楼梯消耗的体力值之和最大,即 maxp∈S∑i=ljrj−1|pi−pi+1|,其中 S 表示将 {hlj,hlj+1,…,hrj} 重新排列能得到的序列的集合。但老 M 在忙着打 MMA,因此他想请你——M 氏混元形意太极拳的第 992844853 个真传弟子,计算这个最大值。
输入格式
第一行两个正整数 n,m,分别表示平台的个数与仰慕者总数。
第二行 n 个正整数 h1∼hn,依次表示平台 1∼n 的高度。
接下来 m 行,第 i 行两个正整数 li,ri(1≤li<ri≤n),表示有新的仰慕者来拜师学艺,你需要回答区间 [1i,ri] 经过重排列后,耗费的最大体力值。
输出格式
m 行,第 i 行一个整数,表示第 i 位仰慕者花费的最大体力值。
样例数据
样例输入
4 4
3 2 2 4
1 3
1 4
2 4
2 3
样例输出
2
5
4
0
样例解释
第一次询问,一种最优的方案为 [2,3,2],耗费体力值为 2。
第二次询问,一种最优的方案为 [3,2,4,2],耗费体力值为 5。
第三次询问,一种最优的方案为 [2,4,2],耗费体力值为 4。
第四次询问,一种最优的方案为 [2,2],耗费体力值为 0。
数据范围
子任务 1(5%):n,m≤10;
子任务 2(10%):hi≤2;
子任务 3(20%):hi≤3;
子任务 4(25%):n,m≤2000;
子任务 5(40%):无附加限制。
对于所有数据,有 2≤n,m≤200000,1≤hi≤109。
保证对于所有询问,满足 1≤li<ri≤n。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 4
3 2 2 4
1 3
1 4
2 4
2 3
2
5
4
0