P5608 [Ynoi2013] 文化课

Chimuzu 省选一轮爆了两个大零蛋，于是滚回去学文化课了。 他翻出一道基础四则运算练习题……然后发现自己不会。 于是他需要你的帮助，作为回报，他会给你 $100$ 分。 前排打广告，有人来看看我写的[融合树](https://www.luogu.org/blog/user3296/rong-ge-shu-fusion-tree)吗 （其实还写了 Brodal queue）

Chimuzu 手上有一个数字序列 $\{a_{1},a_{2},\ldots,a_{n}\}$ 和一个运算符序列 $\{p_{1},p_{2},\ldots,p_{n-1}\}$。其中 $p_{i}$ 只能为 $+$ 或 $\times$。 我们定义一个区间 $[l,r]$ 的权值 $w(l,r)$ 为将字符串 $$ a_{l}~p_{l}~a_{l+1}~p_{l+1} \cdots a_{r-1}~p_{r-1}~a_{r} $$ 写下来之后，按照运算符的优先级计算出的结果。 下面给出一个运算的例子： 若 $a=\{1,3,5,7,9,11\}$，$p=\{+,\times,\times,+,\times\}$，那么有： $$ w(1,6)=1+3\times 5\times 7+9\times 11=205 $$ $$ w(3,6)=5\times 7+9\times 11=134 $$ Chimuzu 需要你对这两个序列进行修改，同时查询某个给定区间的权值。 你需要维护这 $3$ 个操作： 操作一：给定 $l,r,x$，将 $a_{l},a_{l+1},\ldots,a_{r}$ 全部修改成 $x$。 操作二：给定 $l,r,y$：将 $p_{l},p_{l+1},\ldots,p_{r}$ 全部修改成 $y$，$0$ 表示 $+$，$1$ 表示 $\times$。 操作三：给定 $l,r$：查询 $w(l,r) \bmod 1000000007$ 的值。

无

无

#### 样例解释 1 初始的两个序列和前两次操作是题目描述中的例子。第四次操作结束后，两个序列变成了如下形态 $a=\{13,13,5,7,9,11\}$，$p=\{+,\times,\times,\times,\times\}$ $$ w(1,6)=13+13\times 5\times 7\times 9\times 11=45058 $$ $$ w(3,6)=5\times 7\times 9\times 11=3465 $$ ### 数据范围与约定 对于其中 $1\%$ 的数据，为样例 1，时限为 1.5s 对于另外 $14\%$的数据，$n,m\leq 1000$ ，时限为 1.5s 对于另外 $5\%$ 的数据，没有修改操作，时限为 1.5s 对于另外 $14\%$ 的数据，数据保证随机，时限为 1.5s 对于另外 $19\%$ 的数据，没有 1 操作，时限为 1.5s 对于另外 $19\%$ 的数据，没有 2 操作，时限为 1.5s 对于另外 $8\%$ 的数据，时限为 5s 对于另外 $10\%$ 的数据，时限为 3s 对于 $100\%$ 的数据，$n,m\leq 100000$，$1\leq a_{i},x\lt 2^{32}$，$a_{i},x$ 均为奇数，$p_{i},y\in\{0,1\}$，$1\leq l\leq r\leq n$，所有操作 $2$ 还满足 $r\lt n$。时限为 1.5s Idea：Juan_feng。 Solution：nzhtl1477，ccz181078。 Code：Juan_feng，nzhtl1477，rehtorbegnaro，ccz181078。 Data：Juan_feng，nzhtl1477，rehtorbegnaro。