P5069 纵使日薄西山

题面

原题链接 click

题解

普通线段树好题。
首先，题目中的操作可以看成这样：

• 重复执行下一条直至序列全 \(0\)：
• 找到最大值 \(a_u\)，把 \(a_{u-1},a_{u},a_{u+1}\) 都改为 \(0\)，对答案产生贡献 \(a_u\)。

我们考虑用线段树维护这个问题，随即发现区间合并难以处理。
我们发现，难处理的点就在于端点处。
对于线段树上一个区间 \([l,r]\)，维护 \([l,r]\)，\((l,r]\)，\([l,r)\)，\((l,r)\) 的答案，合并时只需看是哪个端点产生贡献即可。
有一个快速判断的方式，就是直接看 \([l,r]\) 和 \([l,r)\) 的答案是否相同就知道 \(r\) 点有没有贡献了。
时间复杂度 \(O(n\log n)\)。需要处理好区间长度较小的情形，此时 Corner Case 较多。

Code

#include<bits/stdc++.h>
using namespace std;
int a[100005],n,q;
struct node{
    long long ans1,ans2,ans3,ans4;
    //ans3是[)，ans2是(]
    int l,r;
    node operator+(const node &b)const{
        node res; res.l=l; res.r=b.r;
        int m=r;
        if(res.r-res.l+1>2){
            if(b.l==b.r){
                res.ans4=ans2;
            }else{
                int tip=2*(ans2!=ans4)+(b.ans3!=b.ans4||a[m+1]==a[m+2]);
                switch(tip){
                    case 0: res.ans4=ans2+b.ans3; break;
                    case 1: res.ans4=ans2+b.ans3; break;
                    case 2: res.ans4=ans2+b.ans3; break;
                    case 3: res.ans4=a[m]>=a[m+1]?ans2+b.ans4:ans4+b.ans3; break;
                }                
            }
        }else res.ans4=0;
        if(b.l==b.r){
            res.ans3=ans1;
        }else{
            int tip=2*(ans1!=ans3)+(b.ans3!=b.ans4||a[m+1]==a[m+2]);
            switch(tip){
                case 0: res.ans3=ans1+b.ans3; break;
                case 1: res.ans3=ans1+b.ans3; break;
                case 2: res.ans3=ans1+b.ans3; break;
                case 3: res.ans3=a[m]>=a[m+1]?ans1+b.ans4:ans3+b.ans3; break;
            }
        }
        if(l==r){
            res.ans2=b.ans1;
        }else{
            int tip=2*(ans2!=ans4)+(b.ans1!=b.ans2||a[m+1]==a[m+2]);
            switch(tip){
                case 0: res.ans2=ans2+b.ans1; break;
                case 1: res.ans2=ans2+b.ans1; break;
                case 2: res.ans2=ans2+b.ans1; break;
                case 3: res.ans2=a[m]>=a[m+1]?ans2+b.ans2:ans4+b.ans1; break;
            }
        }
        int tip=2*(ans1!=ans3)+(b.ans1!=b.ans2||a[m+1]==a[m+2]);
        switch(tip){
            case 0: res.ans1=ans1+b.ans1; break;
            case 1: res.ans1=ans1+b.ans1; break;
            case 2: res.ans1=ans1+b.ans1; break;
            case 3: res.ans1=a[m]>=a[m+1]?ans1+b.ans2:ans3+b.ans1; break;
        }
        return res;
    }
};
node s[300005];
void build(int p,int l,int r){
    if(l==r){
        s[p].l=s[p].r=l; s[p].ans1=a[l]; s[p].ans2=s[p].ans3=s[p].ans4=0;
        return;
    }
    int m=l+r>>1;
    build(p<<1,l,m); build(p<<1|1,m+1,r);
    s[p]=s[p<<1]+s[p<<1|1];
}
void update(int p,int l,int r,int v){
    if(l>v||r<v) return;
    if(l==r){
        s[p].ans1=a[v]; return;
    }
    int m=l+r>>1;
    update(p<<1,l,m,v); update(p<<1|1,m+1,r,v);
    s[p]=s[p<<1]+s[p<<1|1];
}
void print(int p){
    cerr<<"p="<<p<<" l="<<s[p].l<<" r="<<s[p].r<<"\n";
    cerr<<"ans1="<<s[p].ans1<<"  ";
    cerr<<"ans2="<<s[p].ans2<<"  ";
    cerr<<"ans3="<<s[p].ans3<<"  ";
    cerr<<"ans4="<<s[p].ans4<<"  ";
    cerr<<'\n';
    if(s[p].l!=s[p].r){
        print(p<<1); print(p<<1|1);
    }
}
int 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 u,v;
        cin>>u>>v;
        a[u]=v; update(1,1,n,u);
        cout<<s[1].ans1<<'\n';
        // for(int i=1;i<=n;i++) cerr<<a[i]<<' '; cerr<<'\n';
        // print(1);
    }
    return 0;
}