【题解】CF601B Lipshitz Sequence

这种题第一眼看上去不可做，我们考虑证明一个结论：

对于一个区间的 \(Lipschitz\) 常数 \(k\) ,应满足：

即

证明：

考虑三个数的情况，设它们分别是：\(\left\{0,x,\infty\right\}\)

那么，相邻的区间的 \(Lipschitz\) 常数 \(k=\left\{x,\infty-x\right\}\)

而整体区间的 \(Lipschitz\) 常数 \(k=\frac{\infty}{2}\)

那么考虑 \(x\) 的取值会发现，无论 \(x\) 怎么取值，相邻区间的 \(Lipschitz\) 常数 \(k\) 必然要大于整体区间的 \(k.\) 而根据三个数的区间进行推广即可。

证毕。

那么我们接下来的任务就是回答询问了，观察到询问数目很少，所以我们用 \(O(nq)\) 的复杂度就可以了。

考虑如何 \(O(n)\) 回答一组询问：

观察相邻区间的 \(k\) 会出现多少次。我们求出左边和右边第一个大于它的数的位置，那么在这个区间中，任意一个包含它的区间都会让 \(k\) 出现一次。那么如果我们可以 \(O(n)\) 求出这个东西，问题就解决了。

显然单调栈可以完成这个任务。

于是这题做完了。单调栈内部维护数值递减的序列下标，每次弹出栈的时候更新栈顶元素的目标值就好了。

总复杂度：\(O(nq).\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2e5+10;
const int inf=(1<<30);
int n,q,a[MAXN],h[MAXN];
inline int Abs(int x){if(x<0)return -x;return x;}
int st[MAXN],top;
int l[MAXN],r[MAXN];
signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;++i)scanf("%lld",&h[i]);
	for(int i=1;i<n;++i)a[i]=Abs(h[i+1]-h[i]);
	for(;q;q--){
		int L,R;
		scanf("%lld%lld",&L,&R);
		R--;
		memset(l,0,sizeof l);
		memset(r,0,sizeof r);
		int ans=0;
		for(int i=L,j=1;i<=R;++i,++j)a[j]=Abs(h[i+1]-h[i]);
		int len=R-L+1;
		top=0;
		for(int i=1;i<=len;++i){
			while(top&&a[st[top]]<a[i]){
				r[st[top]]=i-st[top];
				top--;
			}
			l[i]=i-st[top];
			st[++top]=i;
		}
		while(top)r[st[top]]=len+1-st[top],top--;
		for(int i=1;i<=len;++i)ans+=a[i]*l[i]*r[i];
		printf("%lld\n",ans);
	}
	return 0;
}

【题解】CF601B Lipshitz Sequence

原文：https://www.cnblogs.com/h-lka/p/14930650.html