TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

71.4% (45/63)

Submission's AC Ratio

29.1% (147/506)

Tags

Description

「動態資料結構」是由 Basch, Julien 於 1999 年提出的一種資料結構,目的是儲存隨著時間變化的資料,譬如一堆直線的堆疊(Heap)之類的都屬於其範疇。

但是,這個有點太難了,目前這個技術在臺灣高中競賽圈並不普及(就算中國大陸算臺灣也是),目前筆者僅知道一名女國手有寫出來。

當然,Kinetic 具有「運動的;運動引起的」的意思,而 Kinetic Energy 則是指我們熟悉的,物理上的動能。在牛頓力學底下,一個物體的動能 EK 被定義為:

EK=12mv2

此處 m 為其質量,v 為其速度。現在,你有 N 個物品由左而右排列,而左邊數來第 i 個的質量為 mi、速度為 vi1iN)。而你還需要測試三個前所未見的科學儀器:

  1. α質量變更器:能將一個區間的物體的質量增加 x
  2. β速度變更器:能將一個區間的物體的速度增加 y
  3. γ動能檢測器:給定一個區間 [l,r]1lrN),會輸出區間中所有物體的動能和。因為數字可能會很大,所以請輸出答案除以 109+7 的餘數即可

你可以寫一個程式支援模擬這三個機器的運作嗎?這些機器總共會用 Q 次。

Input Format

輸入的第一行是兩個正整數,包含 NQ1N,Q105)。接下來兩行各有 N 個正整數,分別是 mivi0vi,mi109)。最後,有 Q 行,可能為下列三種之一:

  1. 1 l r x 代表使用了 α質量變更器,將 [l,r] 這個區間的質量增加 x0x109)。
  2. 2 l r y 代表使用了 β速度變更器,將 [l,r] 這個區間的速度增加 y0y109)。
  3. 3 l r 代表使用了 γ動能檢測器,請輸出 [l,r] 這個區間所有物質的動能和。因為數字可能會很大,所以請輸出答案除 109+7 的餘數即可

對於所有的詢問,皆保證 1lrN,且每一筆測試資料至少會使用一次 γ動能檢測器。

Output Format

對於每一個γ動能檢測器,請輸出檢測結果。

此外,這一題還有部分分數,給分如下:

  • 7 分 - 只有 3 這一種運算
  • 10 分 - NQ106
  • 13 分 - 只有 13 兩種運算
  • 15 分 - 只有 23 兩種運算,且保證所有的 mi=1
  • 20 分 - 只有 23 兩種運算
  • 35 分 - 無額外限制

Sample Input 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 Output 1

3
36

Sample Input 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 2

500000004
999999899

Hints

不知道取餘數下除數字怎麼做嗎?其實 ÷2 這個運算其實就是「乘上一個數字 x,這個 x 要滿足 2x1mod109+7」這個運算(在沒有模的狀況下,這個數字為一個實數 0.512)!祝好運!

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~8 只有 3 這種運算 7
3 0~1, 9~15 NQ106 10
4 2~8, 16~22 只有 13 兩種運算 13
5 23~29 只有 23 兩種運算,且保證所有的 , mi = 1 15
6 2~8, 23~36 只有 23 兩種運算 20
7 0~43 無額外限制 35

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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