問題一覧 > 通常問題

No.749 クエリ全部盛り

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

問題文

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

入力

N Q
q1 l1 r1 k1
...
qQ lQ rQ kQ

1≤N≤106
0≤Q≤105
qi∈{0,1,2,3,4}
0≤li≤ri<N
0≤k≤109
入力は全て整数

クエリ(q,l,r,k)の意味は次の通りである
q=0のとき：k∑i=lraiをmod109+7で出力し改行せよ
q=1のとき：l≤i≤rである全てのiについて、aiをkに変更せよ
q=2のとき：l≤i≤rである全てのiについて、aiをai+kに変更せよ
q=3のとき：l≤i≤rである全てのiについて、aiをai∗kに変更せよ
q=4のとき：l≤i≤rである全てのiについて、aiをai+k∗Fiに変更せよ
ただし{Fn}はフィボナッチ数列であり、F0=0, F1=1, Fn=Fn−1+Fn−2(n≥2)である。


テストケースは全部で20個ある。
うち10個のケースは N≤103 かつ Q≤103 を満たす。（★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もしくは右上の雲マークをクリックしてアカウントを作成してください。