文化课 - 题目

题目描述

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

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

提示

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

QOJ.ac

QOJ

#7479. 文化课