「Codeforces 601B」 Lipshitz Sequence
Description
定义数列 (h[1..n]) 的 Lipschitz 常数为：
现给定一个长度为 (n) 的数列 (h[1..n]) 以及 (q) 个询问。
每个询问给出一个二元组 ((l,r)) ，要求对于每组询问求出所有子序列的 Lipschitz 常数之和，即求 ：
Solution
请务必耐心看完切理解题面。
显然不是暴力可以随随便便搞出来的。
当然你也可以使用 ST 表或者线段树，不过这里介绍的是一种最简单的方法，效率也丝毫不亚于上面二者的方法——单调栈。
首先我们有一个命题，这是我们解题的关键。
- 命题：数列 (a[x..y]) 的
Lipschitz常数必定是由数列中 相邻的两项 计算而来。即 (operatorname{L}(a[x..y])=maxlimits_{xle i<y}leftlceildfrac{|a_i-a_{i+1}|}{2} ight ceil)
接下来给出证明（简单的解释而已，可能不太漂亮）：
不妨将 ((i,a[i])) 视作平面上的一点，这样我们得到 (operatorname{size}(a)) 个点，从而将原命题转化为了这样一个新命题：在上述所有的点中任选两点构成的直线斜率的绝对值之中，最大的必定是由横坐标之差为 (1) 的两点（即相邻的）构成。
这个命题相比之前一个要好证很多。我们取这 (operatorname{size}(a)) 个点中任意三个，令其为 (A,B,C(x_A<x_B<x_C,y_A<y_B<y_C))。(这里只是一种情况，其他情况同理)。
- (k_{AB}<k_{BC}) 的情况：
图中可见， (k_{BC}>k_{AC})。
- (k_{AB}>k_{BC})
（从左至右分别为点 (A,B,C) ）
图中可见， (k_{AB}>k_{AC})。
再将其他情况手玩一下，可以发现，最大的斜率一定为相邻的两点所构成的直线的斜率。
于是我们可以很自然地转化 (operatorname{L}(h[l..r])) 为：(maxlimits_{lle ile r} leftlceildfrac{|h_{i+1}-h_i|}{2} ight ceil)
设 (b_{i}=|h_{i+1}-h_{i}|)
于是原问题就成了求：
行了，经过以上的 瞎扯 ，问题已经原型毕露了。
可以看出这实质上就是一个 一段区间的所有子区间最大值之和 的问题。
那么直接用单调栈正着做一次，反着做一次，得到以任意一位为最小值的最大区间的边界，然后用乘法原理计算出对答案的贡献即可。
复杂度为 (O(n))。
上代码！
Code
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : Codeforces 601B Lipshitz Sequence
*/
#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
const int N=1e5+5;
int a[N],b[N];
int n,q;
#define left LEFT
#define right RIGHT
int left[N],right[N];
long long query(int l,int r)
{
if(l>=r) return 0ll;
int len=r-l;
for(register int i=l;i<r;i++)
b[i-l+1]=abs(a[i+1]-a[i]);
stack<int> st;
for(register int i=1;i<=len;i++)
{
while(!st.empty()&&b[st.top()]<=b[i]) st.pop();
if(!st.empty()) left[i]=st.top();
else left[i]=0;
st.push(i);
}
st=stack<int>();
for(register int i=len;i>=1;i--)
{
while(!st.empty()&&b[st.top()]<b[i]) st.pop();
if(!st.empty()) right[i]=st.top();
else right[i]=len+1;
st.push(i);
}
long long ret=0ll;
for(register int i=1;i<=len;i++)
ret+=b[i]*1ll*(i-left[i])*(right[i]-i);
return ret;
}
signed main()
{
cin>>n>>q;
for(register int i=1;i<=n;i++)
cin>>a[i];
while(q--)
{
int l,r;
cin>>l>>r;
cout<<query(l,r)<<endl;
}
return 0;
}
复杂度 (O(n imes q))
虽然看着不小，但已经足以通过此题了。