P7402题解

· · 题解

原题连接

背景

其他的题解对这道题的做法已经有了大概的讲解，但是对于正解的思路与细节处理说得云里雾里，所以说我将对正解的思路及具体细节作诠释，不再赘述部分分数的解法。

分析

初步转化

看见区间加减，便不由得想到差分，于是建立一个差分数组 d[i]=a[i]-a[i-1] ，这样每次就只需要在两处单点修改。

接着分析，一个区间真正能作出贡献的只有最大值与最小值，也就是说，当我们已经得到一段的极大值与极小值的时候，便应该直接划分，而非继续将其他的数纳入这个区间，最终使得整个划分出来的区间单调不下降或单调不上升。转化为数学语言就是：对于所有划分的区间 [l,r] ，满足 a[l]\le a[l+1]\le \cdots\le [r] 或者 a[l]\ge a[l+1]\ge \cdots\ge a[r] ，接着将其转化为上文的差分思路也就是要满足 d[l+1],d[l+2],\cdots,d[r]同号（根据定义，0 应该与任何数同号）。这样的话每个区间最后的值就应该是 \sum\limits_{i=l+1}^r\left|d[i]\right| 。根据这个式子，我们可以发现，因为题目要求最大值，我们就应该尽量少的剔除差分值，非要减也要减去绝对值较小的差分值。

根据前面的分析，现在就需要我们单点修改，区间查询。那不就是线段树吗？于是我们可以尝试从线段树的角度考虑如何合并两个区间。

线段树分析

假设有这样一个区间（下面表示原数组，上面表示差分数组）：

如果在差分线段树上的话，就会被分成这样两个区间：

那么对应反映在原数组上就是这样：

如果两个差分区间符合上述的“初步转换”中的条件的话就可以直接累加，合并成一个区间（过于简单，没有画出）。

但如果两个差分区间不符合条件也就是需要必须分开的时候，就会有一下两种情况：

这是我们就会发现，对于差分区间，其左右两边的值可能选或不选，那么在处理线段树的时候，我们就应该对应存上左右两端选或不选的情况。

最后再输出整个区间，由于整个区间的左右两端选了的答案一定比不选优（多考虑了两个值），所以直接输出两端都选的情况就行，根本不用作比较。

对了，记得开 \text{long long}

如果还没有理解，就可以看代码。

代码

#include<bits/stdc++.h>
#define int long long//记得开long long 
using namespace std;
const int szl=8e5+5;
int sgt[szl][2][2];//第一维是线段树节点编号，第二位表示左端点状态，第三位表示由端点状态，0表示不选，1表示选 
int a[szl],d[szl],root=1;
void Updata(int p,int mid){
    for(int i=0;i<=1;i++)
        for(int j=0;j<=1;j++)
            if(d[mid]*d[mid+1]>=0)sgt[p][i][j]=sgt[p<<1][i][1]+sgt[p<<1|1][1][j];//可以合并成一个区间 
            else sgt[p][i][j]=max(sgt[p<<1][i][0]+sgt[p<<1|1][1][j],sgt[p<<1][i][1]+sgt[p<<1|1][0][j]); //不能合并成一个区间 
    return;
}
void Add(int p,int l,int r,int pos){
    if(l==r){
        sgt[p][1][1]=abs(d[l]);
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid)Add(p<<1,l,mid,pos);
    else Add(p<<1|1,mid+1,r,pos);
    Updata(p,mid);
    return;
}

signed main(){
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[i]=a[i]-a[i-1];
        if(i==1)continue;
        Add(root,2,n,i);
        //也可以写在外面O(N)建树，但这样写慢却简单，少些一个函数，反正不会超时，减少错误率 
        //注意：差分数组从2到n的区间才有效 。 
    } 
    while(q--){
        int l,r,x;cin>>l>>r>>x;
        if(l>1){
            d[l]+=x;
            Add(root,2,n,l);
        }
        if(r<n){
            d[r+1]-=x;
            Add(root,2,n,r+1);
        }
        cout<<sgt[root][1][1]<<endl;//最后直接输出，不用比较左右端点不选的情况 
    }
    return 0;
}