P10399 『STA - R5』ReLyna


你手中有一个数字 $x$。走到位置 $i$ 时你可以将手中的数字变为 $x+a_i$ 或 $x\times b_i$。 有 $m$ 次操作。 - `1 x y z`，执行 $a_x\gets y$，$b_x\gets z$。 - `2 l r`，查询若你从 $[l,r]$ 的所有子区间中等概率选择一个子区间 $[l',r']$，则你从 $l'$ 走到 $r'$ 后手中的数的最大值的期望是多少？答案对 $10^9+7$ 取模。每次行动开始前你手中的数字都会归零。 如果你不知道有理数如何取模，可以参考 [P2613 有理数取余](https://www.luogu.com.cn/problem/P2613)。 可参考样例解释理解题意。

无

无

**样例解释** 对于第一次询问，令 $f(i,j)$ 为你从 $i$ 开始顺次走到 $j$ 后手中的数的最大值，则答案为 $\frac{1}{3}[f(2,2)+f(2,3)+f(3,3)]=\frac{1}{3}(52+156+8)=72$。 **数据范围** | 子任务编号 | $n$ | $m$ | 特殊性质 | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | Subtask #1 | $50$ | $50$ | 无 | 5 | | Subtask #2 | $500$ | $500$ | 无 | 5 | | Subtask #3 | $10^5$ | $10^5$ | 保证任何时刻 $a_i=1$ | 25 | | Subtask #4 | $10^5$ | $50$ | 无 | 25 | | Subtask #5 | $10^5$ | $10^5$ | 没有修改操作 | 25 | | Subtask #6 | $10^5$ | $10^5$ | 无 | 15 | 对于所有数据，$1\le n,m\le 10^5$，$0