传送门

题意：

给出一个序列A，定义函数 f(A)=∑n−1i=1|ai−ai+1| f ( A ) = ∑ i = 1 n − 1 | a i − a i + 1 |

先给出两种操作：

1.在区间[l,r]内找一个位置，使得把这个位置的值加上x后，f(A)最大，求这个最大值

2.把区间[l,r]加上x

序列长度和询问长度<=1e5

Solution：

对于操作1，我们可以大力分类讨论一下一个位置i与他的左右两边的位置i-1和i+1的关系，我们先考虑简单点：假设 ai+x≥ai+1 ai+x≥ai−1 a i + x ≥ a i + 1   a i + x ≥ a i − 1 ，那么：

1. ai≥ai−1 ai≥ai+1 a i ≥ a i − 1   a i ≥ a i + 1 Δ=2∗x Δ = 2 ∗ x

2. ai<ai−1 ai<ai+1 a i < a i − 1   a i < a i + 1 Δ=2∗x−2∗((ai+1−ai)+(ai−1−ai)) Δ = 2 ∗ x − 2 ∗ ( ( a i + 1 − a i ) + ( a i − 1 − a i ) )

3. ai>ai−1 ai+1>ai a i > a i − 1   a i + 1 > a i Δ=2∗x−2∗(ai+1−ai) Δ = 2 ∗ x − 2 ∗ ( a i + 1 − a i )

那么我们在[2,n-1]中的每个位置，用线段树来维护 max(0,ai+1−ai)+max(0,ai−1−ai) m a x ( 0 , a i + 1 − a i ) + m a x ( 0 , a i − 1 − a i ) 即可

但是在上面我们只考虑了 Δ Δ 为正的结果

需不需要考虑 Δ Δ 为负的结果呢？

部分需要：当[l,r]的长度大于1时，是不会出现 Δ Δ 为负的情况的，因为 Δ Δ 为负只可能在第二种情况中出现，但是在同一个区间不可能所有的点都是第二种情况

所以我们只需要特判一下长度即可

代码中使用了差分，使得修改和维护都变得更简单

注意边界问题

代码：

#include<cstdio>
#include<iostream>
#define debug(x) cerr<<#x<<"="<<x<<" "
using namespace std;
const int N=100010;
int n,q;
struct tree{
    int l,r;
    long long minn;
}tr[4*N];
long long a[N];
int l,r,v,p,x;
long long ans=0;
long long abss(long long x){
  return x<0?-x:x;}
void build(int i,int l,int r)
{
    tr[i].l=l,tr[i].r=r;
    if (l==r) {ans+=abss(a[l]);if (l>1) tr[i].minn=max(0ll,-a[l-1])+max(0ll,a[l]);return;}
    int mid=l+r>>1;
    build(i<<1,l,mid);build(i<<1|1,mid+1,r);
    tr[i].minn=min(tr[i<<1].minn,tr[i<<1|1].minn);
}
void modify(int i,int pos,int x)
{
    int L=tr[i].l,R=tr[i].r;
    if (L==R)
    {
        ans-=abss(a[L]);
        a[L]+=x;
        ans+=abss(a[L]);
        if (pos>1) tr[i].minn=max(0ll,-a[L-1])+max(0ll,a[R]);
        if (x&&pos<n-1) modify(1,pos+1,0);
        return;
    }
    int mid=L+R>>1;
    if (mid>=pos) modify(i<<1,pos,x);
    else modify(i<<1|1,pos,x);
    tr[i].minn=min(tr[i<<1].minn,tr[i<<1|1].minn);
}
long long query(int i,int l,int r)
{
    int L=tr[i].l,R=tr[i].r; 
    if (L>r||l>R) return 1e18;
    if (l<=L&&R<=r) return tr[i].minn;
    long long as=query(i<<1,l,r);
    as=min(as,query(i<<1|1,l,r));
    return as;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) a[i]=a[i+1]-a[i];
    build(1,1,n-1);
    scanf("%d",&q); 
    for (int i=1;i<=q;i++)
    {
        scanf("%d%d%d%d",&p,&l,&r,&x);
        if (p==1)
        {
            if (l==r)
            {
                if (l==1) printf("%I64d\n",ans-abss(a[1])+abss(a[1]-x));
                else if (l==n) printf("%I64d\n",ans-abss(a[n-1])+abss(a[n-1]+x));
                else printf("%I64d\n",ans-abss(a[l])-abss(a[l-1])+abss(a[l-1]+x)+abss(a[l]-x));
            }
            else
            {
                long long del=0;
                del=max(del,2*x-2*query(1,(l>1?l:l+1),r));
                if (l==1) del=max(del,-abss(a[l])+abss(a[l]-x));
                if (r==n) del=max(del,-abss(a[r-1])+abss(a[r-1]+x));
                printf("%I64d\n",ans+del);
            }
        }
        else
        {
            if (l>1) modify(1,l-1,x);
            if (r<n) modify(1,r,-x);
        }
    }
}