线段树区间历史最值

• 在维护 $max,tag$ 的同时再维护 $hismax,histag$
• 合并方式（重要）

void pushdown(int u)
{
    cl.hmax=std::max(cl.hmax,cl.max+cu.htag);
    cr.hmax=std::max(cr.hmax,cr.max+cu.htag);
    cl.htag=std::max(cl.htag,cl.tag+cu.htag);
    cr.htag=std::max(cr.htag,cr.tag+cu.htag);
    cl.max+=cu.tag,cr.max+=cu.tag;
    cl.tag+=cu.tag,cr.tag+=cu.tag;
    cu.htag=cu.tag=0;
}

• 例题： GSS2 - Can you answer these queries II - 洛谷 | 计算机科学教育新生态
  • 注意到“字段和”，也就是要求所有子区间的和的最大值，“所有子区间”容易联想到历史最值线段树
  • 考虑离线，扫描线扫 $r$，设原始输入序列为 $a$，我们用线段树维护一个序列 $b$，序列第 $i$ 个数表示 $a_{i-r}$ 的和，显然如果不考虑去重，区间 $[l,r]$ 历史最值就是所求答案。
  • 考虑如何处理加入一个数：记录这个数上次出现的位置，每次加入时区间加 $[pre_{val}+1,r]$ 即可

线段树区间历史和

• 区间历史操作，从矩阵乘法到标记 - 洛谷专栏
• 关于线段树上的一些进阶操作 - 洛谷专栏