No.749 クエリ全部盛り
タグ : / 解いたユーザー数 42
作問者 : 👑
testestest
/ テスター :
夕叢霧香(ゆうむらきりか)
問題文
すべての要素が$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もしくは右上の雲マークをクリックしてアカウントを作成してください。