Luogu5608 [Ynoi2013] 文化课

题意：维护一个长度为 的，只有 整数，加号和乘号 的算式。

支持下列操作 ：

• 将区间内的数值全部修改为 。

• 将区间内的运算符全部修改为 。

• 查询区间 取出后，按照运算符的优先级计算出的结果。答案对 取模。

，时限 ，空限 。

---

使用线段树维护。

不考虑修改

对于每个线段树节点，维护区间算式的结果。

合并两个区间时，若中间的运算符是加法，则简单相加。

若中间的运算符是乘法，找出连乘前缀后缀，相乘即可。这需要维护连乘前后缀的积。

修改运算符

若区间改为加法，直接将算式结果替换为区间和。

若区间改为乘法，直接将算式结果替换为区间积。

注意要更新连乘前后缀。

修改数值

记 为区间内长为 的极长连乘段的个数，则将区间数值修改为 后算式结果为：

经典自然根号：一些正整数和为 ，则不同的数的个数为 。

故有值的 只有 个（自然根号），复杂度为 。

维护 ，pushup 时用归并合并，时间复杂度同上。

空间复杂度为 。

还有个小问题，我们计算上式时需要计算 的幂，直接使用快速幂会使得复杂度带个 。

注意到我们维护了有序的 ，对于相邻两个有值的 ，快速幂计算 以从 得到 。可以证明这样优化后复杂度变为 。