题解 CF601B 【Lipshitz Sequence】

2020-02-22 11:29:26


Orz _Wallace_!

让我重新翻译一次题面吧。

![pic1](http://47.103.204.220/picture_bed/uploads/2020/02/ $HO2J7_XGZZI1KRTLE~HB_J.png) 来自[这个博客](https://blog.csdn.net/qaq__qaq/article/details/53116479),侵权删除。 那么我们发现,我们要斜率的绝对值最大化。 对于相邻两者斜率相同的情况,直接带入就OK,问题不大。 对于相邻两者斜率不同的情况,我们来手模一下几种情况。 ![pic2](http://47.103.204.220/picture_bed/uploads/2020/02/CF601B2.png) 我们发现黑线的斜率都比不过红线或者绿线的斜率的绝对值! 其实也好性感理解,**因为两者斜率不一样**,一定存在斜率小的那个把斜率大的那个**稀释**掉了。 得到关键条件: ## 一个区间的斜率最大值一定是(相邻两者的斜率)最大值。 那么我们预处理出每一个斜率的最大值就OK了。 对于q个请求,使用单调栈的“靠山”模型来解决。 ![pic1](http://47.103.204.220/picture_bed/uploads/2020/02/CF817D1.png) 假如每个竖的线段的高度代表每一组相邻斜率,我们当前要求斜率的最大值的总和。那么我们需要考虑红的和绿的分别会作为哪些区间的最大值。 红:(2,2) 绿:(2,4)(3,4)(4,4)(2,5)(3,5)(4,5) 我们发现,作为区间最大值的区间数量其实就是 到左边“靠山”的距离 乘上 到右边的“靠山”的距离。 ![pic2](http://47.103.204.220/picture_bed/uploads/2020/02/CF817D2.png) 然后就好啦。 单调栈扫一遍。 需要注意的是,如果所有元素都遍历完了,还有元素在单调栈里,我们需要在$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的题解的图片和代码,请管理员不要误伤。

感谢洛谷提供评测和博客服务。

感谢ISP项目组提供私人图床服务。