题解：P5069 [Ynoi2015] 纵使日薄西山

· · 题解

很有意思的一道题，写篇题解作为纪念。

【1】什么样的数会被“选出”

观察选出数后的操作：

选出序列中最大值的出现位置，若有多个最大值则选位置标号最小的一个，设位置为 x，则将 a_{x-1},a_x,a_{x+1} 的值减 1，如果序列中存在小于 0 的数，则把对应的数改为 0。

发现 a_{x - 1},a_x,a_{x + 1} 之间的大小关系是永远不会变的（a_{x} \geq a_{x - 1} 且 a_{x} \geq a_{x + 1}）。

证明

被选出的所有数显然有如下性质：

  2. 被选出的所有数两两不相邻。

【2】答案满足可合并性

在讲解答案具有可合并性之前，先讲解答案怎么求。

其实很简单，就是所有会被选出的数之和。证明略。

既然是数的和，那么不难想到用线段树维护。

那么它真的可以合并吗？

接下来就要用到一个很恶心但很有用的技巧：分类讨论！

分两类讨论：

  1. 如果左区间的右端点不会被选出，或者右区间的左端点不会被选出，那么两个区间中选出的数不相邻，整个区间中选出的数就是两个区间中选出的数，可直接合并。

  2. 如果左区间的右端点和右区间的左端点都会被选出，那么在这两个选出的点中就只能选一个，显然选的是较大者（由【1】中的性质 1 即得）。

    这样的两区间也可以合并，但这相当于我们要求出将左区间（除右端点之外）的所有数归零所需要的次数和将右区间（除左端点之外）的所有数归零所需要的次数，更多的细节请看下一部分：

【3】恶心的合并（push_up）操作

本题的 push_up 是一个细节超多的部分，也是本题的关键，接下来会尽我所能讲解如何合并两个序列的答案。

为方便理解下文，我们记线段树节点需要维护的 4 种区间值对应的形态如下：

我们记 val_u(k)(k \in \{0,1,2,3\}) 为线段树节点 u 维护区间的第 k 种形态选出的数的和。

并且，因为合并需要判断左区间的右端点和右区间的左端点是否被选出，所以我们还需要维护 l_u(k) \in \{0,1\} 表示将线段树节点 u 维护区间的第 k 种形态归零是否会选中左端点，r_u(k) \in \{0,1\} 同理。

【3.0】一些显然的结论

再来看这张图：

显然，l_u(1) = 0（都不用归零了是怎么选上左端点的）。

同理，r_u(2) = 0,l_u(3) = r_u(3) = 0。

【3.1】特判叶节点

显然，对于叶节点 leaf，有 val_{leaf}(0) = a_i（a_i 为对应在序列上的位置），val_{leaf}(1) = val_{leaf}(2) = val_{leaf}(3) = 0（区间长度为 1，左端点和右端点重合，任意一个不清零都代表整个区间不清零）。

【3.2】完善分类讨论

接下来讨论对于非叶节点维护的区间。

对于求 val_u(0),l(0),r(0)：

如果将左区间（形态 0）清零不选右端点（如下图）或将右区间（形态 0）清零不选左端点，那么那么两个区间中选出的数不相邻，整个区间中选出的数就是两个区间中选出的数，可直接合并（合并方法即 val_u(0) = val_{lc}(0) + val_{rc}(0)）。

对于 l_u(0)，就是对应形态（形态 0）左区间的 l_{lc}(0)，同理可得 r_u(0) 是对应形态（形态 0）的 r_{rc}(0)。

否则，左右区间相邻的两点都选了，按照【2】中的分类讨论，我们应该选较大者。

如果选的是左区间右端点，那么右区间左端点就自然被清零了，无需考虑在右区间内如何清零左端点，所以右区间应该是形态 1（左端点不用清零）,左区间是形态 0。合并的操作就是 val_u(0) = val_{lc}(0) + val_{rc}(1),l_u(0) = l_{lc}(0),r_u(0) = r_{rc}(1)。

如果选的是右区间左端点，同理，左区间右端点是不用在左区间清零的，所以左区间是形态 2，右区间是形态 0。合并的操作就是 val_u(0) = val_{lc}(2) + val_{rc}(0),l_u(0) = l_{lc}(2,r_u(0) = r_{rc}(0。

以下是这部分的代码：

//转移得到t[root].val[0] 
if(t[lchild].r[0] && t[rchild].l[0]){//左右区间将所有数清零选了相邻的点 ，只能选一个 
    if(a[mid] >= a[mid + 1]){//选左区间的右端点更优，所以不选右区间左端点 
        t[root].l[0] = t[lchild].l[0];//当前区间左端点选不选取决于（将左区间所有数归零是否选左端点） 
        t[root].r[0] = t[rchild].r[1];//当前区间右端点选不选取决于（将右区间除左端点之外所有数归零是否选右端点）
        t[root].val[0] = t[lchild].val[0] + t[rchild].val[1];
    }
    else{//否则不选左区间右端点 
        t[root].l[0] = t[lchild].l[2];
        t[root].r[0] = t[rchild].r[0];
        t[root].val[0] = t[lchild].val[2] + t[rchild].val[0];
    }
}
else{//否则直接合并 
    t[root].l[0] = t[lchild].l[0];
    t[root].r[0] = t[rchild].r[0];
    t[root].val[0] = t[lchild].val[0] + t[rchild].val[0];
}

对于 val(1,2,3),l(1,2,3),r(1,2,3) 是同理的，可以自行画图并结合完整代码理解。

【4】完整代码

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 1e5 + 9;
int n,q;
int a[N];
struct node{
    int val[4];
    bool l[4],r[4];
    //val[0]：将当前区间所有数归零所需要的次数
    //val[1]：将当前区间（除左端点之外）的所有数归零所需要的次数
    //val[2]：将当前区间（除右端点之外）的所有数归零所需要的次数
    //val[3]：将当前区间（除两端点之外）的所有数归零所需要的次数 

    //l[0]：将当前区间所有数归零是否会选左端点 
} t[N << 2];
void push_up(int root,int l,int r){
    //转移得到t[root].val[0] 
    if(t[lchild].r[0] && t[rchild].l[0]){//左右区间将所有数清零选了相邻的点 ，只能选一个 
        if(a[mid] >= a[mid + 1]){//选左区间的右端点更优，所以不选右区间左端点 
            t[root].l[0] = t[lchild].l[0];//当前区间左端点选不选取决于（将左区间所有数归零是否选左端点） 
            t[root].r[0] = t[rchild].r[1];//当前区间右端点选不选取决于（将右区间除左端点之外所有数归零是否选右端点）
            t[root].val[0] = t[lchild].val[0] + t[rchild].val[1];
        }
        else{//否则不选左区间右端点 
            t[root].l[0] = t[lchild].l[2];
            t[root].r[0] = t[rchild].r[0];
            t[root].val[0] = t[lchild].val[2] + t[rchild].val[0];
        }
    }
    else{//否则直接合并 
        t[root].l[0] = t[lchild].l[0];
        t[root].r[0] = t[rchild].r[0];
        t[root].val[0] = t[lchild].val[0] + t[rchild].val[0];
    }

    //转移得到t[root].val[1]
    t[root].l[1] = false;//当前区间左端点不选
    if(t[lchild].r[1] && t[rchild].l[0]){//左区间将除左端点之外的所有数清零，右区间将所有数清零选了相邻的点 ，只能选一个 
        if(a[mid] >= a[mid + 1]){//选左区间的右端点更优，所以不选右区间左端点
            t[root].r[1] = t[rchild].r[1];//当前区间右端点选不选取决于（将右区间除左端点之外所有数归零是否选右端点）
            t[root].val[1] = t[lchild].val[1] + t[rchild].val[1];
        }
        else{//否则不选左区间右端点
            t[root].r[1] = t[rchild].r[0];//当前区间右端点选不选取决于（将右区间除所有数归零是否选右端点）
            t[root].val[1] = t[lchild].val[3] + t[rchild].val[0];
        }
    }
    else{//否则直接合并 
        t[root].r[1] = t[rchild].r[0];
        t[root].val[1] = t[lchild].val[1] + t[rchild].val[0];
    }

    //转移得到t[root].val[2]
    t[root].r[2] = false;//当前区间右端点不选
    if(t[lchild].r[0] && t[rchild].l[2]){//左区间将所有数清零，右区间将除右端点之外的所有数清零选了相邻的点 ，只能选一个 
        if(a[mid] >= a[mid + 1]){//选左区间的右端点更优，所以不选右区间左端点
            t[root].l[2] = t[lchild].l[0];
            t[root].val[2] = t[lchild].val[0] + t[rchild].val[3];
        }
        else{//否则不选左区间右端点
            t[root].l[2] = t[lchild].l[2];
            t[root].val[2] = t[lchild].val[2] + t[rchild].val[2];
        }
    }
    else{//否则直接合并 
        t[root].l[2] = t[lchild].l[0];
        t[root].val[2] = t[lchild].val[0] + t[rchild].val[2];
    }

    //转移得到t[root].val[3]
    //当前区间左右端点都不选
    t[root].l[3] = false;
    t[root].r[3] = false;
    if(t[lchild].r[1] && t[rchild].l[2]){//左区间将除左端点之外的所有数清零，右区间将除右端点之外的所有数清零选了相邻的点 ，只能选一个 
        if(a[mid] >= a[mid + 1])//选左区间的右端点更优，所以不选右区间左端点
            t[root].val[3] = t[lchild].val[1] + t[rchild].val[3];
        else//否则不选左区间右端点
            t[root].val[3] = t[lchild].val[3] + t[rchild].val[2];
    }
    else//否则直接合并 
        t[root].val[3] = t[lchild].val[1] + t[rchild].val[2];
}
void update(int root,int l,int r,int pos){
    if(l == r){
        t[root].val[0] = a[l];
        t[root].l[0] = t[root].r[0] = true;
        return;
    }
    if(pos <= mid)
        update(lchild,l,mid,pos);
    else
        update(rchild,mid + 1,r,pos);
    push_up(root,l,r);
}
void build(int root,int l,int r){
    if(l == r){
        t[root].val[0] = a[l];
        t[root].l[0] = t[root].r[0] = true;
        //一个点既是左端点也是右端点，所以val[1] = val[2] = val[3] = 0
        return;
    }
    build(lchild,l,mid);
    build(rchild,mid + 1,r);
    push_up(root,l,r);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    build(1,1,n);
    cin >> q;
    while(q--){
        int pos,v;
        cin >> pos >> v;
        a[pos] = v;
        update(1,1,n,pos);
        cout << t[1].val[0] << '\n';
    }
    return 0;
}