問題一覧 > 通常問題

No.749 クエリ全部盛り

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : testestesttestestest / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
9 ProblemId : 2239 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-11-09 22:34:43

問題文

すべての要素が$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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。