[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$ 的值。

输入输出格式

输入格式


第一行包含两个整数 $n,m$。 第二行包含 $n$ 个整数 $a_{1},a_{2},\ldots,a_{n}$。 第三行包含 $n-1$ 个整数 $p_{1},p_{2},\cdots,p_{n-1}$,$0$ 表示 $+$, $1$ 表示 $\times$。 接下来 $m$ 行,每行有一个操作。 一开始输入一个标识符 $op$,表示操作类型,接着按照题目描述输入各操作的参数。 $op=1$ 时,输入 $3$ 个整数 $l,r,x$,表示将 $a_{l},a_{l+1},\ldots,a_{r}$ 全部修改成 $x$。 $op=2$ 时,输入 $3$ 个整数 $l,r,y$,表示将 $p_{l},p_{l+1},\ldots,p_{r}$ 全部修改成 $y$,$0$ 表示 $+$,$1$ 表示 $\times$。 $op=3$ 时,输入 $2$ 个整数 $l,r$,表示查询 $w(l,r) \bmod 1000000007$ 的值。

输出格式


对于每一次操作 $3$,输出 $1$ 行 $1$ 个整数表示所求答案。

输入输出样例

输入样例 #1

6 6
1 3 5 7 9 11
0 1 1 0 1
3 1 6
3 3 6
1 1 2 13
2 3 4 1
3 1 6
3 3 6

输出样例 #1

205
134
45058
3465

输入样例 #2

20 20
525160717 947806001 1495853547 5283947 39115023 1008063001 397093019 1434942997 247321621 145181297 359967329 642658073 1402873249 50886569 150383317 1004954721 351661441 1660759179 48867601 1316622161 
0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 
3 2 19
3 2 15
3 9 9
1 16 16 394339135
2 1 19 0
3 1 15
1 4 11 564942769
3 7 7
2 2 19 0
3 1 1
3 9 9
1 9 9 705415201
1 3 18 152081579
1 13 17 905666497
1 11 17 612267547
1 2 20 111949431
2 1 1 0
1 10 17 838945201
2 4 18 0
3 2 18

输出样例 #2

900803889
834560968
247321621
852589651
564942769
525160717
564942769
719106438

说明

#### 样例解释 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。