P4314 CPU监控（线段树维护历史最大值）

木xx木大 · 2021-07-03 08:16:49 · 题解

P4314 CPU监控

发现以前写得太不清楚了以至于复习的时候看不懂自己写了啥，看题解也没太看懂，于是决定重新学一下然后自己写篇题解。

本篇题解参考 关于线段树上的一些进阶操作

先考虑如果只有加操作怎么做。假设每个点开了一个队列，存这个点被打过的所有标记，那么 pushdown 操作即为将父亲节点的队列中的元素全部放进儿子节点的队列，每放入一个值，则更新 x\leftarrow x'+tag,mx\leftarrow\max(mx,x)。但我们不可能真的存一个队列。设队列中加法标记的前缀和为 s[1\dots k]，则所有更新进行完后应有 x\leftarrow x'+s_k,mx\leftarrow\max\{x'+s_i\}=x'+\max\{s_i\}。那么我们只需要维护历史加的最大值即可。这个东西怎么维护呢？考虑合并两个队列（的前缀和）s_{son}[1\dots k_1],s_{fa}[1\dots k_2] 的过程

则 \max\{s_{son}[i]\}=\max(\max \{s'_{son}[i]\},s_{son}'[k_1]+\max\{s_{fa}[i]\}) ，则我们需要维护 s_{son}[k_1] ，即目前的加法标记即可。总结一下，代码如下

void getsum(int ro,int sum,int hsum)//hsum:父节点上一次pushdown后的历史加法标记最大值
{
   t[ro].hsum=max(t[ro].hsum,t[ro].sum+hsum);//历史加法标记最大值
   t[ro].ans[1]=max(t[ro].ans[1],t[ro].ans[0]+hsum);//历史最大值
   t[ro].ans[0]+=sum;//当前最大值
   t[ro].sum+=sum; //当前加法标记
}

再加上赋值操作后，如果队列中有两种标记，不便于处理。可以发现，若存在一个赋值标记，则这个区间中的所有数会变成一样的，那么之后的加法标记都可以看成赋值标记。因此，此时的队列可以表示为一个加法标记队列紧跟着一个赋值标记队列。加法标记按上面说的处理。对于赋值标记 a[1\dots k]，最终产生的贡献即为 max\{a_i\}，再维护一个历史最大赋值标记即可。

#include<bits/stdc++.h>
#define inl inline
#define mid (t[ro].l+t[ro].r)/2
using namespace std;
namespace FGF
{
    int n,m;
    const int N=1e5+5;
    const int INF=0x3f3f3f3f;
    int read()
    {
        int s=0,w=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')w=-w;ch=getchar();}
        while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
        return s*w;
    }
    struct tree{
        int l,r,sum,hsum,val,hval,ans[2];
        bool vis;
    }t[N<<2]; 
    int a[N];
    inl void pushup(int ro)
    {
        t[ro].ans[0]=max(t[ro<<1].ans[0],t[ro<<1|1].ans[0]);//当前最值 
        t[ro].ans[1]=max(t[ro<<1].ans[1],t[ro<<1|1].ans[1]);//历史最值 
    }
    void build(int ro,int l,int r)
    {
        t[ro].l=l,t[ro].r=r;
        if(l==r)
        {
            t[ro].ans[0]=t[ro].ans[1]=a[l];
            return;
        }
        build(ro<<1,l,mid),build(ro<<1|1,mid+1,r);
        pushup(ro);
    }
    inl void getsum(int ro,int sum,int hsum)//hsum:父节点上一次pushdown后的最大加和 
    {
        if(t[ro].vis)//是否进行过区间赋值操作 
        {
            t[ro].hval=max(t[ro].hval,t[ro].val+hsum);
            t[ro].ans[1]=max(t[ro].ans[1],t[ro].ans[0]+hsum);
            t[ro].ans[0]+=sum;
            t[ro].val+=sum;
        }
        else
        {
            t[ro].hsum=max(t[ro].hsum,t[ro].sum+hsum);
            t[ro].ans[1]=max(t[ro].ans[1],t[ro].ans[0]+hsum);
            t[ro].ans[0]+=sum;
            t[ro].sum+=sum;
        }
    }
    inl void getval(int ro,int val,int hval)//hval:父节点上一次pushdown后的最大赋值 
    {
        if(t[ro].vis)t[ro].hval=max(t[ro].hval,hval);
        else t[ro].vis=1,t[ro].hval=hval;
        t[ro].ans[1]=max(t[ro].ans[1],hval);
        t[ro].ans[0]=t[ro].val=val;
     }
    inl void pushdown(int ro)
    {
        getsum(ro<<1,t[ro].sum,t[ro].hsum);
        getsum(ro<<1|1,t[ro].sum,t[ro].hsum);
        t[ro].sum=t[ro].hsum=0;
        if(t[ro].vis)
        {
            getval(ro<<1,t[ro].val,t[ro].hval);
            getval(ro<<1|1,t[ro].val,t[ro].hval);
            t[ro].val=t[ro].hval=0,t[ro].vis=0;
        }
    }
    void add(int ro,int l,int r,int x)
    {
        if(t[ro].l>=l&&t[ro].r<=r)
        {
            getsum(ro,x,x);
            return;
        }
        pushdown(ro);
        if(l<=mid)add(ro<<1,l,r,x);
        if(r>mid)add(ro<<1|1,l,r,x);
        pushup(ro);
    }
    void updat(int ro,int l,int r,int x)
    {
        if(t[ro].l>=l&&t[ro].r<=r)
        {
            getval(ro,x,x);
            return;
        }
        pushdown(ro);
        if(l<=mid)updat(ro<<1,l,r,x);
        if(r>mid)updat(ro<<1|1,l,r,x);
        pushup(ro);
    }
    int query(int ro,int l,int r,int op)
    {
        if(t[ro].l>=l&&t[ro].r<=r)return t[ro].ans[op];
        pushdown(ro);
        int s=-INF;
        if(l<=mid)s=query(ro<<1,l,r,op);
        if(r>mid)s=max(s,query(ro<<1|1,l,r,op));
        return s;
    }
    void work()
    {
        n=read();
        for(int i=1;i<=n;i++)
            a[i]=read();
        build(1,1,n);
        m=read();
        while(m--)
        {
            char s[5];
            int x,y;
            scanf("%s",s);x=read(),y=read();
            if(s[0]=='Q')printf("%d\n",query(1,x,y,0));
            if(s[0]=='A')printf("%d\n",query(1,x,y,1));
            if(s[0]=='P')add(1,x,y,read());
            if(s[0]=='C')updat(1,x,y,read());
        }
    }
}
int main()
{
    FGF::work();
    return 0;
}