P5069 [Ynoi2015] 纵使日薄西山

纵使日薄西山,我也想保护你..

先不考虑单点修改

手玩一下样例

可以发现你一直操作一个数的结果是和答案一样的

可以大致证明一下

x y z

如果选择y操作，那么x,z必然不能操作，因为x,z会和y一直减少，只有y做出了贡献,所以我们的答案应该是选的数之和

因此应该只有2种操作方法

操作1 ，3，5，7...

操作2，4，6，8...

也就是维护一个奇偶性相同的单增或者单减序列

挺抽象的，这种做法待补

我们可以用线段树来维护需要被操作的值（合并很妙）

我们先思考一下，我们需要维护哪些值，左端点有没有被操作的，右端点有没有被操作的，以及如果左端点需要被操作的贡献是多少，右端点需要被操作的贡献是多少，如果两端都被操作的贡献是多少，因此我们维护四颗线段树，seg[N=a[mid+1]){ seg[id][2].lf=seg[tl(id)][0].lf; seg[id][2].val=seg[tl(id)][0].val+seg[tr(id)][3].val; }else{ seg[id][2].lf=seg[tl(id)][2].lf; seg[id][2].val=seg[tl(id)][2].val+seg[tr(id)][2].val; }

else()直接转移

if(seg[tl(id)][0].rf && seg[tr(id)][2].lf){
        if(a[mid]>=a[mid+1]){
            seg[id][2].lf=seg[tl(id)][0].lf;
            seg[id][2].val=seg[tl(id)][0].val+seg[tr(id)][3].val;
        }else{
            seg[id][2].lf=seg[tl(id)][2].lf;
            seg[id][2].val=seg[tl(id)][2].val+seg[tr(id)][2].val;
        }

4.if() 要管左边的左子树有右端点标记，要管右边的右子树有左端点标记

不用考虑左右端点转移

（i）左边大于等于右边

答案求和是左边（管左边）+右边（管两边）

（ii）右边大于左边

答案求和是左边（管两边）+右边（管右边）

if(seg[tl(id)][1].rf && seg[tr(id)][2].lf){
        if(a[mid]>=a[mid+1]){
            seg[id][3].val=seg[tl(id)][1].val+seg[tr(id)][3].val;
        }else{
            seg[id][3].val=seg[tl(id)][3].val+seg[tr(id)][2].val;
        }

else()直接转移

 seg[id][3].val=seg[tl(id)][1].val+seg[tr(id)][2].val;

讨论结束

可以发现只有中间存在重叠的情况才需要讨论左右端点的标记转移，其他情况直接转移即可

文字描述很拉垮，可以直接看码.

完整代码

#include
#include
#include
#include
#include
#include
#define INF (1ll