【死亡笔记☠】线段树历史区间最值小记🐤

线段树历史区间最值：支持区间加法，询问区间内历史上的最大值，清空历史

不要草率！！！比看上去的要难无数倍！！！

注意事项：

1. 一定要记录两个标记 $tag$ 和 $mxtag$，分别为“区间加标记”和“区间最大加标记”（后者也可以理解为这个区间内所有来过的加标记的前缀最大值）

2. 正确的 pushdown 方法：

void pushdown(int k)    {        if(tag[k]||mxtag[k]){ // !!!X: if(tag[k])            mxtag[k1]=max(mxtag[k1],tag[k1]+mxtag[k]); // !!!X: mxtag[k1]+=mxtag[k] / mxtag[k1]=max(mxtag[k1],tag[k1]+tag[k])            tag[k1]+=tag[k];            hismx[k1]=max(hismx[k1],maxv[k1]+mxtag[k]); // !!!X: hismx[k1]=max(hismx[k1],maxv[k1]) / hismx[k1]=max(hismx[k1],maxv[k1]+tag[k])            maxv[k1]+=tag[k]; // !!!X: maxv[k1]+=mxtag[k]                        mxtag[k2]=max(mxtag[k2],tag[k2]+mxtag[k]);            tag[k2]+=tag[k];            hismx[k2]=max(hismx[k2],maxv[k2]+mxtag[k]);            maxv[k2]+=tag[k];                        tag[k]=mxtag[k]=0;        }    }

　　今天，你死亡了吗

3. 正确的 update 方法：

        maxv[k]=max(maxv[k1],maxv[k2]);        //!!!X hismx[k]=max(hismx[k],maxv[k]);        hismx[k]=max(hismx[k1],hismx[k2]);   

4. 在 $[x1,x2]$ 时间修改 $[y1,y2]$，在 $x$ 时间询问 $[y1,y2]$，用的就是这个历史最值线段树，普通线段树搞不定！！！

5. 清空的方法：全局加上一个很大的值 $Delta$（注意 $Delta$ 一定要很大，大于所有修改加之和） ，这样以前的历史最值都被它所淹没了，只留下当下的最值还有效，然后询问时结果减回 $Delta$ 即可。