题解 | 牛客挑战赛55

A

显然斐波那契数列。

B

函数的值不超过 ，枚举函数的层数。 先统计多少模 同余，模 同余,...,层数是 级别。 用哈希表存然后统计答案即可。

C

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

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

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

D

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

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


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

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

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

导致结果的变化量为

导致结果的变化量为

可以写出最终的式子:



(注意 是前面式子后单独的，不是 )

修改时给定，现在只要 `pushup` 时能维护 就做完了。

右儿子部分，直接加上就完事，左儿子部分还要多乘一个 ，这个也可以 `pushup` 时维护，直接左儿子乘右儿子。

E

F

考虑莫队，假定我们已经处理出区间 的答案，考虑去扩展到 的答案。

定义





我们转移的代价为：



将 提出 。



而对于



的处理是平凡的。

令


那么前面的部分即



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

具体地：

令

那么



对于 处理可以直接莫队二离做到 。