题解 CF601B 【Lipshitz Sequence】

Orz \_Wallace_! 让我重新翻译一次题面吧。  来自[这个博客](https://blog.csdn.net/qaq__qaq/article/details/53116479)，侵权删除。 那么我们发现，我们要斜率的绝对值最大化。 对于相邻两者斜率相同的情况，直接带入就OK，问题不大。 对于相邻两者斜率不同的情况，我们来手模一下几种情况。  我们发现黑线的斜率都比不过红线或者绿线的斜率的绝对值！ 其实也好性感理解，**因为两者斜率不一样**，一定存在斜率小的那个把斜率大的那个**稀释**掉了。 得到关键条件： ## 一个区间的斜率最大值一定是（相邻两者的斜率）最大值。 那么我们预处理出每一个斜率的最大值就OK了。 对于q个请求，使用单调栈的“靠山”模型来解决。  假如每个竖的线段的高度代表每一组相邻斜率，我们当前要求斜率的最大值的总和。那么我们需要考虑红的和绿的分别会作为哪些区间的最大值。 红：(2,2) 绿：(2,4)(3,4)(4,4)(2,5)(3,5)(4,5) 我们发现，作为区间最大值的区间数量其实就是 到左边“靠山”的距离 乘上 到右边的“靠山”的距离。  然后就好啦。 单调栈扫一遍。 需要注意的是，如果所有元素都遍历完了，还有元素在单调栈里，我们需要在$n+1$的位置放一个“巨型靠山”，否则会出错。 ``` #include<bits/stdc++.h> #define int long long using namespace std; const int N=105005; int n,q,v[N],b[N]; int st[N],Right[N],Left[N],top,pos[N]; signed main(){ cin>>n>>q; for(int i=1;i<=n;++i) scanf("%lld",&v[i]); for(int i=1;i<=n-1;++i) b[i]=abs(v[i+1]-v[i]); for(int _=1,l,r,ans=0;_<=q;++_){ memset(Left,0,sizeof(Left)); memset(Right,0,sizeof(Right)); scanf("%lld%lld",&l,&r); r--;//由于是线段变区间，所以要-1 ans=0; for(int i=l,j=1;i<=r;++i,++j)//把[l,r]变成[1,nn],方便操作 b[j]=abs(v[i+1]-v[i]); int nn=r-l+1; for(int i=1;i<=nn;++i){ while(top!=0&&st[top]<b[i]){//维护单调栈递减。st[]表示单调栈，存放元素的具体数值。top表示顶指针。 Right[pos[top]]=i-pos[top];//Right[]是右边的靠山。 top--; } Left[i]=i-pos[top];//Left[]是左边的靠山。 st[++top]=b[i]; pos[top]=i; } while(top)//栈内剩余元素处理（巨型靠山） Right[pos[top]]=nn+1-pos[top],top--; for(int i=1;i<=nn;++i)//计算贡献 ans+=(b[i]*(Left[i])*(Right[i])); cout<<ans<<endl; } } ``` ## 后记 我运用了一点昨天写的[CF817D的题解](https://53058.blog.luogu.org/solution-cf817d)的图片和代码，请管理员不要误伤。 感谢洛谷提供评测和博客服务。 感谢ISP项目组提供私人图床服务。