86. 一維陣列區間加值區間乘值區間查詢總和

一維陣列區間加值區間乘值區間查詢總和

• 給你一個一維陣列，你有三個操作可以做：增加某一區間的值、將某區間的值都乘上一個數、求一個區間的總和
• 小心TLE

輸入說明:

• 輸入的第一行會有一個正整數$n$($1 \leq n \leq 1000000$)，表示給定陣列$S$的大小是$n$
• 陣列索引值編號從1開始
• 接著會有一行，有$n$個int範圍的整數，第$i$個整數代表陣列$S[i]$的值
• 接著有一個整數$t$($0<t \leq 300000$)，表示接下來有$t$個指令要執行
• 指令有三種:
  • 1 x y c：將$S[x] \sim S[y]$的值增加$c$，$|c| \leq 2147483647$，$1 \leq x \leq y \leq n$
  • 2 x y w：將$S[x] \sim S[y]$的值乘上$w$，$|w| \leq 2147483647$，$1 \leq x \leq y \leq n$
  • 3 x y：查詢區間$S[x] \sim S[y]$中其元素總和，$1 \leq x \leq y \leq n$

輸出說明

• 對於每個3開頭的指令，請輸出查詢的結果(由於值可能很大，請$mod ~~ (10^9+7)$再輸出)，記得換行

範例輸入:

5
1 2 3 4 5
19
1 1 5 3
2 1 5 3
1 1 2 2
2 1 3 3
1 3 5 -1
2 2 4 2
1 2 4 9
2 3 5 8
3 1 1
3 2 2
3 3 3
3 4 4
3 5 5
3 1 5
3 1 4
3 1 3
3 1 2
3 2 4
3 3 5

範例輸出:

42
111
920
392
184
1649
1465
1073
153
1423
1496

配分:

配分	限制
20%	$1 \leq n \leq 100$
20%	$1 \leq n \leq 1000$
60%	沒有限制

• 2017/08/17 Update：修正題目範圍錯誤，去除不合理的TLE時限。

Judge Setting

run-time limit: 800 ms
memory limit: 31447232 byte
測資數量: 0