题目链接)
数据范围，2e5
区间越长越省力。
对于一个起点来说，从这里搭tizi最远到达的是序列中右侧第一个大于它的数所在的位置。
用单调栈可以找到这样的区间，这些区间大致如下所示。
就是最多只会有包含的情况，但是不会出现交叉的情况。
然后可以这样渐次登高，到达最顶端。
下降的时候就是从末尾倒着再用一遍单调栈求出左侧第一个大于本身的数字所在位置。
统计答案时可以选取可以减少体力最大的m个区间，
一个区间减少的体力为，没有体力的体力消耗-区间两端的山峰高度差。
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 2e5+10;
int n , m , top1 , top2 , tot;
int h[N] , Stack1[N] , Stack2[N];
long long Sum[N];
struct Node
{
int l , r; long long val;
Node(int l = 0 , int r = 0 , long long val = 0ll) : l(l) , r(r) , val(val) {}
bool operator < (const Node &A) const { return val > A.val; }
}p[N];
inline int Abs(int x) { return x < 0 ? -x : x; }
int main()
{
long long Answer = 0ll;
scanf("%d%d" , &n , &m);
for(int i = 1 ; i <= n ; ++i) scanf("%d" , &h[i]);
for(int i = 2 ; i <= n ; ++i) Sum[i] = Sum[i-1] + Abs(h[i] - h[i-1]);
top1 = top2 = 0;
for(int i = 1 ; i <= n ; ++i)
{
if(top1 == 0 || h[Stack1[top1]] <= h[i])
Stack1[++top1] = i;
}
for(int i = n ; i >= Stack1[top1] ; --i)
{
if(top2 == 0 || h[Stack2[top2]] <= h[i])
Stack2[++top2] = i;
}
for(int i = 2 ; i <= top1 ; ++i)
p[++tot] = Node(Stack1[i - 1] , Stack1[i] , Sum[Stack1[i]] - Sum[Stack1[i-1]] - Abs(h[Stack1[i]] - h[Stack1[i-1]]));
for(int i = top2 ; i >= 2 ; --i)
p[++tot] = Node(Stack2[i] , Stack2[i - 1] , Sum[Stack2[i-1]] - Sum[Stack2[i]] - Abs(h[Stack2[i]] - h[Stack2[i-1]]));
sort(p + 1 , p + 1 + tot);
Answer = Sum[n];
for(int i = 1 ; i <= min(m , tot) ; ++i)
Answer -= p[i].val;
printf("%lld\n" , Answer);
return 0;
}