A

显然斐波那契数列。

B

函数的值不超过 $\log \backslash log$，枚举函数的层数。 先统计多少模 $cc$ 同余，模 $c^{2}c^2$ 同余,...,层数是 $\log \backslash log$ 级别。 用哈希表存然后统计答案即可。

C

因为是要乘积最大，且因为取模不能直接维护，再观察一下题目的 $22$ 的幂性质，不难发现先取 ${}_2\backslash log\_2$ 。

这样问题变为了切割一个矩形，内部不能包含 $00$（因为乘 $00$ 就变 $00$ 了），且矩形所有数的和最大。

容易发现最大矩形一定是极大矩形，二维前缀和+悬线法dp/单调栈维护即可。

D

发现函数嵌套后关于 $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 时维护，直接左儿子乘右儿子。

E

F

考虑莫队，假定我们已经处理出区间 $[l,r][l,r]$ 的答案，考虑去扩展到 $[l,r+1][l,r+1]$ 的答案。

定义

我们转移的代价为：

将 $S_1[r+1]-S_1[i-1]S\_1[r+1]\; -\; S\_1[i-1]$ 提出 $\max \backslash max$ 。

而对于

的处理是平凡的。

令

那么前面的部分即

我们发现这样对这一部分的处理同样是平凡的。

具体地：

令 $Pre[i]={\sum }_{j=1}^i[S[r+1]>S[i]],Ps[i]={\sum }_{j=1}^i[S[r+1]>S[i]]a[j]Pre[i]=\backslash sum\_\{j=1\}^i[S[r+1]>S[i]],Ps[i]=\backslash sum\_\{j=1\}^i[S[r+1]>S[i]]a[j]$

那么

对于 $Pre,PsPre,Ps$ 处理可以直接莫队二离做到 $O(n^{1.5})O(n^\{1.5\})$ 。