2203 . 動態資料結構（Kinetic Data Structure）
TopCoder
Tags
Description
「動態資料結構」是由 Basch, Julien 於 1999 年提出的一種資料結構，目的是儲存隨著時間變化的資料，譬如一堆直線的堆疊（Heap）之類的都屬於其範疇。
但是，這個有點太難了，目前這個技術在臺灣高中競賽圈並不普及（就算中國大陸算臺灣也是），目前筆者僅知道一名女國手有寫出來。
當然，Kinetic 具有「運動的；運動引起的」的意思，而 Kinetic Energy 則是指我們熟悉的，物理上的動能。在牛頓力學底下，一個物體的動能 $E_K$ 被定義為：
$$E_K = \frac{1}{2}mv^ 2 $$
此處 $m$ 為其質量，$v$ 為其速度。現在，你有 $N$ 個物品由左而右排列，而左邊數來第 $i$ 個的質量為 $m_i$、速度為 $v_i$（$1 \le i \le N$）。而你還需要測試三個前所未見的科學儀器：
- $\alpha-$質量變更器：能將一個區間的物體的質量增加 $x$
- $\beta-$速度變更器：能將一個區間的物體的速度增加 $y$
- $\gamma-$動能檢測器：給定一個區間 $[l, r]$（$1 \le l \le r \le N$），會輸出區間中所有物體的動能和。因為數字可能會很大，所以請輸出答案除以 $10^ 9 + 7$ 的餘數即可。
你可以寫一個程式支援模擬這三個機器的運作嗎？這些機器總共會用 $Q$ 次。
Input Format
輸入的第一行是兩個正整數，包含 $N$ 和 $Q$ （$1 \le N, Q \le 10^ 5$）。接下來兩行各有 $N$ 個正整數，分別是 $m_i$ 與 $v_i$（$0 \le v_i, m_i \le 10^ 9$）。最後，有 $Q$ 行，可能為下列三種之一：
1 l r x代表使用了 $\alpha-$質量變更器，將 $[l, r]$ 這個區間的質量增加 $x$（$0 \le x \le 10^ 9$）。2 l r y代表使用了 $\beta-$速度變更器，將 $[l, r]$ 這個區間的速度增加 $y$（$0 \le y \le 10^ 9$）。3 l r代表使用了 $\gamma-$動能檢測器，請輸出 $[l,r]$ 這個區間所有物質的動能和。因為數字可能會很大，所以請輸出答案除 $10^ 9 + 7$ 的餘數即可。
對於所有的詢問，皆保證 $1 \leq l \leq r \leq N$，且每一筆測試資料至少會使用一次 $\gamma-$動能檢測器。
Output Format
對於每一個$\gamma-$動能檢測器，請輸出檢測結果。
此外，這一題還有部分分數，給分如下：
- $7$ 分 - 只有
3這一種運算 - $10$ 分 - $NQ \leq 10^ 6$
- $13$ 分 - 只有
1和3兩種運算 - $15$ 分 - 只有
2和3兩種運算，且保證所有的 $m_i = 1$ - $20$ 分 - 只有
2和3兩種運算 - $35$ 分 - 無額外限制
Sample Input 1
0 0 0
0 0 0
1 1 3 2
2 1 3 1
3 1 3
1 1 3 2
2 1 3 2
3 1 2
Sample Output 1
36
Sample Input 2
0
0
1 1 1 1
2 1 1 1
3 1 1
1 1 1 1000000000
2 1 1 1000000000
3 1 1
Sample Output 2
999999899
Hints
不知道取餘數下除數字怎麼做嗎？其實 $\div 2$ 這個運算其實就是「乘上一個數字 $x$，這個 $x$ 要滿足 $2 \cdot x \equiv 1 \mod 10^ 9 + 7$」這個運算（在沒有模的狀況下，這個數字為一個實數 $0.5$ 或 $\frac{1}{2} $）！祝好運！
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~8 | 只有 3 這種運算 |
7 |
| 3 | 0~1, 9~15 | $NQ \leq 10^ 6$ | 10 |
| 4 | 2~8, 16~22 | 只有 1 和 3 兩種運算 |
13 |
| 5 | 23~29 | 只有 2 和 3 兩種運算，且保證所有的 , $m_i$ = 1 |
15 |
| 6 | 2~8, 23~36 | 只有 2 和 3 兩種運算 |
20 |
| 7 | 0~43 | 無額外限制 | 35 |