历史值问题
历史值：在维护序列 \(A\) 的同时，在每次操作后，序列 \(A\) 会对序列 \(B\) 的对应位置产生贡献。
-
历史版本和：每次操作后，\(B_i \leftarrow B_i + A_i\)。
-
历史最大值：每次操作后，\(B_i =\max(B_i,A_i)\)。
历史版本和：
给定操作 ： ①区间加。② 查询区间和。 ③查询区间历史版本和。
记 \(ms\) 为区间历史版本和，\(s\) 为区间和，\(len\) 为区间大小。
标记 \(t\) 会令 \(s \leftarrow s+t\times len\)。
标记 \(upd\) 会令 \(ms \leftarrow ms+s\)。
考虑标记队列 \(q[1...k]=\{ t_1,t_2,upd,t_4,upd \}\)。
记 \(S_t[i]\) 为前 \(i\) 个标记中，加法标记的和。
假设给线段树上一个节点加入该标记队列。
对于 \(ms\) 的贡献为
对于 \(s\) 的贡献为 \(S_t[k]\times len\)。
记一个标记队列的 \(mt=\sum\limits_{i=1,q[i]=upd}^k S_t[i]\)，$ud= \sum_{i=1}^k[q[i]=upd] \(，\)tg$ 表示 \(S_t[k]\)。
所以：
\(ms=ms+s\times ud + len\times mt\)。
\(s =len\times tg\)。
所以对于一个标记队列，我们需要记录 \(mt,ud,tg\) 。
考虑两个标记序列的合并。
将 \(u\) 处的标记下传到 \(v\) 处，相当于将 \(u\) 的队列接在 \(v\) 的队列的后面
首先显然 \(ud_v=ud_v+ud_u , tg_v=tg_v+tg_u\)
对于序列 \(q_1[1..k_1]\) 和 \(q_2[1...k_2]\) 合并成 \(q3[1...k_1+k_2]\)。
考虑 \(mt=\sum\limits_{i=1,q[i]=upd}^k S_t[i]\)，显然对于 \(i>k_1\)，\(S_t[i]\) 都会加上 \(t_1+...+t_{k_1}\) ，即 \(tg_1\)。
所以 \(mt_v=mt_v+mt_u+tg_v\times ud_u\) 。
struct node{
LL ms,s,mt,tg,ud; int len;
void add(LL tg2,LL mt2,LL ud2){
ms+=s*ud2+len*mt2;
mt+=tg*ud2+mt2;
ud+=ud2;
s+=tg2*len;
tg+=tg2;
}
} tr[4*N+5];
可能无法区间赋值操作？ 目前看到的都是转化成区间加。
完整代码+例题 P3246 HNOI2016 序列
历史最大值
例题：P4314 CPU监控
先不考虑区间赋值操作。
对于一个线段树上节点，记 \(hm\) 表示历史最大值，\(mx\) 表示最大值。
同样的，考虑加法标记队列 \(t[1...k]\)，和加法前缀和标记队列 \(St[1...k]\)。
我们处理掉这些标记后，\(mx\leftarrow mx+St[k],hm\leftarrow \max(hm,mx+\max\limits_{i=1}^k St[i])\) 。
所以对于一个标记队列，我们记\(tg=St[k],mt=mx+\max\limits_{i=1}^k St[i]\)。
这样我们就可以下传标记了。将 \(u\) 处的标记下传到 \(v\) 处：
\(tg_v=tg_v+tg_u,mt_v=\max(mt_v,tg_v+mu_u)\)。
考虑上区间赋值操作。
考虑到若出现一个覆盖标记后，之后的整个区间都会变成相同的数。这样之后的加标记也能转化成覆盖标记。
考虑标记队列为加法队列后面接一个覆盖标记队列。
考虑覆盖标记队列 \(c[1...k]\) 。
只需要知道 \(c[k]\) 和 \(\max\limits_{i=1}^k c[i]\) 即可。
记 \(cx=c[k] , mc=\max\limits_{i=1}^k c[i]\) 。
现在把两种标记融合起来，详细见代码。
struct node{
int hm,mx,tg,mt,cx,mc;
void add(int tg2,int mt2){
hm=max(hm,mx+mt2); mx+=tg2;
if(mc==-inf) mt=max(mt,tg+mt2),tg+=tg2;
else mc=max(mc,cx+mt2),cx+=tg2;
}
void cov(int cx2,int mc2){
hm=max(hm,mc2); cx=mx=cx2;
mc=max(mc,mc2);
}
} tr[4*N+5];