No.749 クエリ全部盛り

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 19
作問者 : testestesttestestest / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
3 ProblemId : 2239 / 出題時の順位表

問題文

すべての要素が$0$で初期化された長さ$N$の数列$\{a_i\}_{i=0}^{N-1}$に対し、$Q$個のクエリを処理せよ

入力

$N$ $Q$
$q_1$ $l_1$ $r_1$ $k_1$
...
$q_Q$ $l_Q$ $r_Q$ $k_Q$

$1\leq N\leq 10^6$
$0\leq Q\leq 10^5$
$q_i \in \{0,1,2,3,4\}$
$0\leq l_i\leq r_i< N$
$0\leq k \leq 10^9$
入力は全て整数

クエリ$(q,l,r,k)$の意味は次の通りである
$q=0$のとき:$k\sum_{i=l}^{r}a_i$を$\mod 10^9+7$で出力し改行せよ
$q=1$のとき:$l\leq i\leq r$である全ての$i$について、$a_i$を$k$に変更せよ
$q=2$のとき:$l\leq i\leq r$である全ての$i$について、$a_i$を$a_i+k$に変更せよ
$q=3$のとき:$l\leq i\leq r$である全ての$i$について、$a_i$を$a_i*k$に変更せよ
$q=4$のとき:$l\leq i\leq r$である全ての$i$について、$a_i$を$a_i+k*F_i$に変更せよ
ただし$\{F_n\}$はフィボナッチ数列であり、$F_0=0,\ F_1=1,\ F_n=F_{n-1}+F_{n-2} (n\geq 2)$である。


テストケースは全部で20個ある。
うち10個のケースは $N\leq 10^3$ かつ $Q\leq 10^3$ を満たす。(★2くらい)

出力

クエリを処理せよ

サンプル

サンプル1
入力
5 5
1 0 2 3
2 1 3 1
3 0 1 2
4 2 4 2
0 1 3 2
出力
38

各クエリにより数列は次のように変化する。
$\{0,0,0,0,0\}\\ \{3,3,3,0,0\}\\ \{3,4,4,1,0\}\\ \{6,8,4,1,0\}\\ \{6,8,6,5,6\}$

サンプル2
入力
1000000 20
4 359471 684726 491381080
1 409194 601926 917565989
0 135463 321888 288655811
0 394349 521374 932477099
4 399576 593770 745147335
0 4942 864793 41822405
1 829464 948381 376118299
0 436494 767172 738319909
3 121220 700989 148573041
0 139030 302916 790535508
4 707671 790846 877035358
0 28809 102020 969776242
2 439930 622579 490581891
0 404296 961224 251978919
4 613570 750113 563397295
1 50064 717205 790676632
3 249673 934546 400250755
2 302615 388704 165894970
4 10286 930329 517008122
4 784365 959138 63130254
出力
0
775465869
711055457
444030161
0
0
403409237

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。