2203 . 動態資料結構（Kinetic Data Structure）

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

71.4% (45/63)

Submission's AC Ratio

29.1% (147/506)

Tags

CKcon 2021-CKcon

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$ 分 - 只有 1 和 3 兩種運算
  • $15$ 分 - 只有 2 和 3 兩種運算，且保證所有的 $m_i = 1$
  • $20$ 分 - 只有 2 和 3 兩種運算
  • $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

不知道取餘數下除數字怎麼做嗎？其實 $\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

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
Submit out of contest
Back to Top