#P5608. [Ynoi2013] 文化课

[Ynoi2013] 文化课

题目背景

Chimuzu 省选一轮爆了两个大零蛋,于是滚回去学文化课了。

他翻出一道基础四则运算练习题……然后发现自己不会。

于是他需要你的帮助,作为回报,他会给你 100100 分。

前排打广告,有人来看看我写的融合树

(其实还写了 Brodal queue)

题目描述

Chimuzu 手上有一个数字序列 {a1,a2,,an}\{a_{1},a_{2},\ldots,a_{n}\} 和一个运算符序列 {p1,p2,,pn1}\{p_{1},p_{2},\ldots,p_{n-1}\}。其中 pip_{i} 只能为 ++×\times

我们定义一个区间 [l,r][l,r] 的权值 w(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}a=\{1,3,5,7,9,11\}p={+,×,×,+,×}p=\{+,\times,\times,+,\times\},那么有:

w(1,6)=1+3×5×7+9×11=205w(1,6)=1+3\times 5\times 7+9\times 11=205 w(3,6)=5×7+9×11=134w(3,6)=5\times 7+9\times 11=134

Chimuzu 需要你对这两个序列进行修改,同时查询某个给定区间的权值。

你需要维护这 33 个操作:

操作一:给定 l,r,xl,r,x,将al,al+1,,ara_{l},a_{l+1},\ldots,a_{r} 全部修改成 xx

操作二:给定 l,r,yl,r,y:将 pl,pl+1,,prp_{l},p_{l+1},\ldots,p_{r} 全部修改成 yy00 表示 ++11 表示 ×\times

操作三:给定 l,rl,r:查询 w(l,r)mod1000000007w(l,r) \bmod 1000000007 的值。

输入格式

第一行包含两个整数 n,mn,m

第二行包含 nn 个整数 a1,a2,,ana_{1},a_{2},\ldots,a_{n}

第三行包含 n1n-1 个整数 p1,p2,,pn1p_{1},p_{2},\cdots,p_{n-1}00 表示 ++11 表示 ×\times

接下来 mm 行,每行有一个操作。

一开始输入一个标识符 opop,表示操作类型,接着按照题目描述输入各操作的参数。

op=1op=1 时,输入 33 个整数 l,r,xl,r,x,表示将al,al+1,,ara_{l},a_{l+1},\ldots,a_{r} 全部修改成 xx

op=2op=2 时,输入 33 个整数 l,r,yl,r,y,表示将 pl,pl+1,,prp_{l},p_{l+1},\ldots,p_{r} 全部修改成 yy00 表示 ++11 表示 ×\times

op=3op=3 时,输入 22 个整数 l,rl,r,表示查询 w(l,r)mod1000000007w(l,r) \bmod 1000000007 的值。

输出格式

对于每一次操作 33,输出 1111 个整数表示所求答案。

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
205
134
45058
3465
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

900803889
834560968
247321621
852589651
564942769
525160717
564942769
719106438

提示

样例解释 1

初始的两个序列和前两次操作是题目描述中的例子。第四次操作结束后,两个序列变成了如下形态

a={13,13,5,7,9,11}a=\{13,13,5,7,9,11\}p={+,×,×,×,×}p=\{+,\times,\times,\times,\times\}

$$w(1,6)=13+13\times 5\times 7\times 9\times 11=45058 $$w(3,6)=5×7×9×11=3465w(3,6)=5\times 7\times 9\times 11=3465

数据范围与约定

对于其中 1%1\% 的数据,为样例 1,时限为 1.5s

对于另外 14%14\%的数据,n,m1000n,m\leq 1000 ,时限为 1.5s

对于另外 5%5\% 的数据,没有修改操作,时限为 1.5s

对于另外 14%14\% 的数据,数据保证随机,时限为 1.5s

对于另外 19%19\% 的数据,没有 1 操作,时限为 1.5s

对于另外 19%19\% 的数据,没有 2 操作,时限为 1.5s

对于另外 8%8\% 的数据,时限为 5s

对于另外 10%10\% 的数据,时限为 3s

对于 100%100\% 的数据,n,m100000n,m\leq 1000001ai,x<2321\leq a_{i},x\lt 2^{32}ai,xa_{i},x 均为奇数,pi,y{0,1}p_{i},y\in\{0,1\}1lrn1\leq l\leq r\leq n,所有操作 22 还满足 r<nr\lt n。时限为 1.5s

Idea:Juan_feng。

Solution:nzhtl1477,ccz181078。

Code:Juan_feng,nzhtl1477,rehtorbegnaro,ccz181078。

Data:Juan_feng,nzhtl1477,rehtorbegnaro。