UOJ Logo LFYZ Online Judge

LFYZOJ

#322. 【模板】线段树EX(月面战争)

统计

问题描述

这是千年之前的事了。紫玩弄着虚与实的境界,飞去入侵照映湖面的月球。虽然聚集了大量妖怪,不过面对月之近代兵器,结果惨败。至此之后,妖怪们就很少再去入侵不属于自己的领域了。因为这骚动,人类之间也知道了这只境界妖怪的力量。

八云紫聚集了一些妖怪,这些妖怪分布在 $n$ 个位置上,每个位置上的妖怪都有一个原本的战斗力。

紫妈会对这些妖怪进行 $m$ 次操作,操作有两类:

八云紫向幽幽子询问区间 $i$ 到 $j$ 妖怪的战斗力(一个区间的妖怪的战斗力为这个区间内每个妖怪的战斗力之积);

八云紫让伊吹萃香把区间 $i$ 到 $j$ 妖怪的战斗力变成原来的 $k$ 倍。

$P.S.$ 由于战斗力之积可能过大,输出战斗力时请 $mod$ $100007$ 。

输入格式

第一行是整数$n$和$m$代表妖怪的位置数目和询问的个数。

第二行是$n$个整数,第$i$个代表$i$号位置上妖怪的战斗力。

下来$m$行,每行包括3或4个整数。

操作一:格式 $1 $ $x $ $ y$ 含义:输出区间$[x,y]$内每个妖怪的战斗力的积取模所得的结果;

操作二:格式 $2 $ $x $ $ y $ $ k$ 含义:将区间$[x,y]$内每个妖怪的战斗力变为原先的 $k$ 倍。

输出格式

对于每个操作一,输出一个整数,代表那个询问的答案。每输出完一个答案换行。

样例一

input

7 5
1 19 12 5 13 1 2
1 1 3
2 3 6 2
2 1 4 3
1 2 5
1 1 6

output

228
896
5376

数据范围与约定

对于$30\%$的数据,$n \leq 3000$,$m \leq 700$,$1 \leq k \leq 10000$。

对于$60\%$的数据,$n \leq 3000$,$m \leq 40000$,$1 \leq k \leq 10000$。

对于$100\%$的数据,$n \leq 100000$,$m \leq 100000$,$1 \leq k \leq 100000$,所有妖怪初始战斗力小于 $10000$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$