题解 | #【模板】区间一次函数复合求值#

发现函数嵌套后关于 $xx$ 还是一个函数，而且是一次函数。这个自己推一下易证。

于是就可以线段树维护单点修改和区间查询了。

现在问题在于区间加 $bb$，这个不好 pushdown。

考虑区间加后对合并后函数的变化。

$kk$ 值显然不变，$bb$ 值可以考虑每个函数被加 $xx$ 的贡献，来尝试维护 $bb$ 的变化量。

$b_{l}b\_l$ 导致结果的变化量为 $x\times k_{l+1}\times k_{l+2}\mathrm{.}\mathrm{.}\mathrm{.}x\; \backslash times\; k\_\{l+1\}\; \backslash times\; k\_\{l+2\}\; ...$

$b_{l+1}b\_\{l+1\}$ 导致结果的变化量为 $x\times k_{l+2}\times k_{l+3}\mathrm{.}\mathrm{.}\mathrm{.}x\; \backslash times\; k\_\{l+2\}\; \backslash times\; k\_\{l+3\}\; ...$

可以写出最终的式子:

$x\times {\sum }_{i=l}^{r-1}{\prod }_{j=i+1}^r{k}_j+xx\; \backslash times\; \backslash sum\backslash limits\_\{i=l\}^\{r-1\}\; \backslash prod\backslash limits\_\{j=i+1\}^r\; k\_j+x$

(注意 $+x+x$ 是前面式子后单独的，不是 $k_j+xk\_j+x$)

$xx$ 修改时给定，现在只要 pushup 时能维护 ${\sum }_{i=l}^{r-1}{\prod }_{j=i+1}^r{k}_j+1\backslash sum\backslash limits\_\{i=l\}^\{r-1\}\; \backslash prod\backslash limits\_\{j=i+1\}^r\; k\_j+1$ 就做完了。

右儿子部分，直接加上就完事，左儿子部分还要多乘一个 ${\prod }_{i=mid+1}^r{k}_i\backslash prod\backslash limits\_\{i=mid+1\}^r\; k\_i$，这个也可以 pushup 时维护，直接左儿子乘右儿子。