TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

68.2% (15/22)

Submission's AC Ratio

22.9% (25/109)

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$)。而你還需要測試三個前所未見的科學儀器:

  1. $\alpha-$質量變更器:能將一個區間的物體的質量增加 $x$
  2. $\beta-$速度變更器:能將一個區間的物體的速度增加 $y$
  3. $\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. 1 l r x 代表使用了 $\alpha-$質量變更器,將 $[l, r]$ 這個區間的質量增加 $x$($0 \le x \le 10^ 9$)。
  2. 2 l r y 代表使用了 $\beta-$速度變更器,將 $[l, r]$ 這個區間的速度增加 $y$($0 \le y \le 10^ 9$)。
  3. 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$ 分 - 只有 13 兩種運算
  • $15$ 分 - 只有 23 兩種運算,且保證所有的 $m_i = 1$
  • $20$ 分 - 只有 23 兩種運算
  • $35$ 分 - 無額外限制

Sample Input

Sample 1:
3 6
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 2:
1 6
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

Sample 1:
3
36

Sample 2:
500000004
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 只有 13 兩種運算 13
5 23~29 只有 23 兩種運算,且保證所有的 , $m_i$ = 1 15
6 2~8, 23~36 只有 23 兩種運算 20
7 0~43 無額外限制 35

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 3 7
1 2000 524288 65536 1 3 7
2 2000 524288 65536 2 4 6 7
3 2000 524288 65536 2 4 6 7
4 2000 524288 65536 2 4 6 7
5 2000 524288 65536 2 4 6 7
6 2000 524288 65536 2 4 6 7
7 2000 524288 65536 2 4 6 7
8 2000 524288 65536 2 4 6 7
9 2000 524288 65536 3 7
10 2000 524288 65536 3 7
11 2000 524288 65536 3 7
12 2000 524288 65536 3 7
13 2000 524288 65536 3 7
14 2000 524288 65536 3 7
15 2000 524288 65536 3 7
16 2000 524288 65536 4 7
17 2000 524288 65536 4 7
18 2000 524288 65536 4 7
19 2000 524288 65536 4 7
20 2000 524288 65536 4 7
21 2000 524288 65536 4 7
22 2000 524288 65536 4 7
23 2000 524288 65536 5 6 7
24 2000 524288 65536 5 6 7
25 2000 524288 65536 5 6 7
26 2000 524288 65536 5 6 7
27 2000 524288 65536 5 6 7
28 2000 524288 65536 5 6 7
29 2000 524288 65536 5 6 7
30 2000 524288 65536 6 7
31 2000 524288 65536 6 7
32 2000 524288 65536 6 7
33 2000 524288 65536 6 7
34 2000 524288 65536 6 7
35 2000 524288 65536 6 7
36 2000 524288 65536 6 7
37 2000 524288 65536 7
38 2000 524288 65536 7
39 2000 524288 65536 7
40 2000 524288 65536 7
41 2000 524288 65536 7
42 2000 524288 65536 7
43 2000 524288 65536 7