#1747. 爬楼梯

    ID: 1747 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1090来源:qoj.ac数据:公开样例线段树分块

爬楼梯

爬楼梯

题目描述

标题: 爬楼梯 - Problem - QOJ.ac

#5405. 爬楼梯

Statistics

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