P5608 [Ynoi2013] Cultural Classes.

Chimuzu messed up badly in the first round of the NOI Qualifier, getting two big zeros, so he went back to study cultural classes. He dug out a basic four-operations arithmetic practice problem... and then found that he could not do it. So he needs your help. As a reward, he will give you $100$ points. Advertisement at the top: would anyone like to take a look at the [fusion tree](https://www.luogu.org/blog/user3296/rong-ge-shu-fusion-tree) I wrote? (Actually, I also wrote about the Brodal queue.)

Chimuzu has a number sequence $\{a_{1},a_{2},\ldots,a_{n}\}$ and an operator sequence $\{p_{1},p_{2},\ldots,p_{n-1}\}$. Each $p_{i}$ can only be $+$ or $\times$. We define the weight $w(l,r)$ of an interval $[l,r]$ as the result obtained by writing the string $$ a_{l}~p_{l}~a_{l+1}~p_{l+1} \cdots a_{r-1}~p_{r-1}~a_{r} $$ and then evaluating it according to operator precedence. An example is given below: If $a=\{1,3,5,7,9,11\}$ and $p=\{+,\times,\times,+,\times\}$, then: $$ w(1,6)=1+3\times 5\times 7+9\times 11=205 $$ $$ w(3,6)=5\times 7+9\times 11=134 $$ Chimuzu needs you to modify these two sequences and also query the weight of a given interval. You need to maintain these $3$ operations: Operation 1: given $l,r,x$, set $a_{l},a_{l+1},\ldots,a_{r}$ all to $x$. Operation 2: given $l,r,y$, set $p_{l},p_{l+1},\ldots,p_{r}$ all to $y$, where $0$ means $+$ and $1$ means $\times$. Operation 3: given $l,r$, query the value of $w(l,r) \bmod 1000000007$.

The first line contains two integers $n,m$. The second line contains $n$ integers $a_{1},a_{2},\ldots,a_{n}$. The third line contains $n-1$ integers $p_{1},p_{2},\cdots,p_{n-1}$, where $0$ means $+$ and $1$ means $\times$. Then follow $m$ lines, each describing one operation. Each operation starts with an identifier $op$, indicating the operation type, followed by the parameters as described above. When $op=1$, input $3$ integers $l,r,x$, meaning to set $a_{l},a_{l+1},\ldots,a_{r}$ all to $x$. When $op=2$, input $3$ integers $l,r,y$, meaning to set $p_{l},p_{l+1},\ldots,p_{r}$ all to $y$, where $0$ means $+$ and $1$ means $\times$. When $op=3$, input $2$ integers $l,r$, meaning to query the value of $w(l,r) \bmod 1000000007$.

For each operation $3$, output $1$ line containing $1$ integer, which is the required answer.

#### Sample Explanation 1 The initial two sequences and the first two operations are the example in the statement. After the fourth operation, the two sequences become: $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 $$ ### Constraints and Notes For $1\%$ of the testdata, it is Sample 1, and the time limit is 1.5s. For another $14\%$ of the testdata, $n,m\leq 1000$, and the time limit is 1.5s. For another $5\%$ of the testdata, there are no modification operations, and the time limit is 1.5s. For another $14\%$ of the testdata, the testdata is guaranteed to be random, and the time limit is 1.5s. For another $19\%$ of the testdata, there is no operation 1, and the time limit is 1.5s. For another $19\%$ of the testdata, there is no operation 2, and the time limit is 1.5s. For another $8\%$ of the testdata, the time limit is 5s. For another $10\%$ of the testdata, the time limit is 3s. For $100\%$ of the testdata, $n,m\leq 100000$, $1\leq a_{i},x\lt 2^{32}$, and both $a_{i}$ and $x$ are odd, $p_{i},y\in\{0,1\}$, $1\leq l\leq r\leq n$. Also, for all operations $2$, it additionally holds that $r\lt n$. The time limit is 1.5s. Idea: Juan_feng. Solution: nzhtl1477, ccz181078. Code: Juan_feng, nzhtl1477, rehtorbegnaro, ccz181078. Data: Juan_feng, nzhtl1477, rehtorbegnaro. Translated by ChatGPT 5