大抄线段树历史值问题

Shui_Dream / 2023-08-21 / 原文

历史值问题

历史值：在维护序列 $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$ 的贡献为

\[\sum\limits_{i=1,q[i]=upd}^k s+S_t[i]\times len \]

\[s(\sum_{i=1}^k[q[i]=upd]) + len\times \sum\limits_{i=1,q[i]=upd}^k S_t[i] \]

对于 $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];

record