QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 64 MB Total points: 100

# 7479. 文化课

Statistics

题目描述

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

样例输入 #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

样例输入 #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。