题解 P4314 【CPU监控】

Froggy · 2020-01-12 09:51:23 · 题解

这道题一开始的想法肯定是用当前最大值及当前的标记维护历史最大值，如果你真这样写，就会WA成 20pts，毕竟是道黑题，不可能这么简单！

举个反例：

8
1 1 10 1 1 1 1 1
3
P 1 8 100
P 1 8 -10
A 3 3

显然，答案是110，但如果按刚才那样维护的话就会输出100,因为第二个操作把会减小第一个操作的add标记，儿子的历史最大值得不到及时的更新，就会WA掉

所以，每个节点还要记录历史最大add标记

同理，还要记录历史最大覆盖标记

先记牢含义：（很好记吧，就是"字面"意思）

注：h是history的意思

add 当前加法标记
hadd 历史最大加法标记
cov 当前覆盖标记
hcov 历史最大覆盖标记
iscov 当前是否覆盖标记，值为true/false
mx 当前区间最大值
hmx 历史区间最大值

两种询问照常，取区间mx/hmx的最大值即可,注意题目中只说值都在int范围内，所以保险起见，inf 要取 INT_MAX (2147483647)

int Qmax(int i,int l,int r){
    if(tree[i].l>=l&&tree[i].r<=r){
        return tree[i].mx;
    }
    pushdown(i);
    int ans=-inf;
    int mid=(tree[i].l+tree[i].r)>>1;
    if(l<=mid){
        ans=max(ans,Qmax(i*2,l,r));
    }
    if(r>mid){
        ans=max(ans,Qmax(i*2+1,l,r));
    }
    return ans;
}
int Qhmax(int i,int l,int r){
    if(tree[i].l>=l&&tree[i].r<=r){
        return tree[i].hmx;
    }
    pushdown(i);
    int ans=-inf;
    int mid=(tree[i].l+tree[i].r)>>1;
    if(l<=mid){
        ans=max(ans,Qhmax(i*2,l,r));
    }
    if(r>mid){
        ans=max(ans,Qhmax(i*2+1,l,r));
    }
    return ans;
}

儿子更新父亲也照常，直接取max即可:

inline void update(int i){
    tree[i].mx=max(tree[i*2].mx,tree[i*2+1].mx);
    tree[i].hmx=max(tree[i].hmx,tree[i].mx);
   //或tree[i].hmx=max(tree[i*2].hmx,tree[i*2+1].hmx);
}

重点是如何pushdown

先介绍一个好科技: 成员函数，可以使代码看起来条理更清晰，并大大减少码量，不过可能会稍微慢一点，加一些 inline 就没关系啦

pushdown的时候重点是要分类讨论：之前是否被覆盖过，即由 iscov 标记决定

先讲覆盖的时候：（要传 d 和 hd ,表示用于更新的当前覆盖值和用于更新的历史覆盖最大值）

如果iscov为true：用hd更新hcov，取max
如果iscov为false：iscov变为true，hcov变为hd

此外还要更新历史最大值hmx，(和hd取max)

加法的时候更复杂一些：d 和 hd 的含义同理

如果iscov为true：说明之前被覆盖过了，此时相当于用d+cov进行Cover即可
如果iscov为false：此时只有加法，用mx+hd和add+hd分别更新hmx和had,并更新mx和add标记 (把mx和add加上d)

最后，pushdown以后别忘记清空标记！！


//结构体里的成员函数：
struct node{
    ...
    inline void Cover(int d,int hd){//覆盖
        if(iscov){
            hcov=max(hcov,hd);
        }
        else{
            iscov=true;
            hcov=hd;
        }
        hmx=max(hmx,hd);
        cov=mx=d;
        add=0;
    }
    inline void Add(int d,int hd){//辅助Change执行加法
        hadd=max(hadd,add+hd);
        hmx=max(hmx,mx+hd);
        add+=d,mx+=d;
    }
    inline void Change(int d,int hd){//加法的分类讨论
        if(iscov)Cover(cov+d,cov+hd);
        else Add(d,hd);
    }
   /*其实还可以把Change和Add合并，泥萌别把意思混了就好*/
}

//下放标记
void pushdown(int i){
    //先下放加法
    tree[i*2].Change(tree[i].add,tree[i].hadd);
    tree[i*2+1].Change(tree[i].add,tree[i].hadd);
    tree[i].add=tree[i].hadd=0;//清空
   //再下放覆盖
    if(tree[i].iscov){
        tree[i*2].Cover(tree[i].cov,tree[i].hcov);
        tree[i*2+1].Cover(tree[i].cov,tree[i].hcov);
        tree[i].iscov=tree[i].cov=tree[i].hcov=0;//清空标记
    }
}

如何区间修改调用Change和Cover就不说了把，贴个code

void _plus(int i,int l,int r,int d){
    if(tree[i].l>=l&&tree[i].r<=r){
        tree[i].Change(d,d);
        return;
    }
    pushdown(i);
    int mid=(tree[i].l+tree[i].r)>>1;
    if(l<=mid){
        _plus(i*2,l,r,d);
    }
    if(r>mid){
        _plus(i*2+1,l,r,d);
    }
    update(i);
}
void Cover(int i,int l,int r,int d){
    if(tree[i].l>=l&&tree[i].r<=r){
        tree[i].Cover(d,d);
        return ;
    }
    pushdown(i);
    int mid=(tree[i].l+tree[i].r)>>1;
    if(l<=mid){
        Cover(i*2,l,r,d);
    }
    if(r>mid){
        Cover(i*2+1,l,r,d);
    }
    update(i);
}

然后...就完了。代码就贴剪切板里了 here

Froggy's blog

题解 P4314 【CPU监控】

重点是如何pushdown

呱!!