TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

95.0% (19/20)

Submission's AC Ratio

30.4% (52/171)

Description

你玩過植物大戰殭屍嗎?

這是一款用植物打趴殭屍的熱門遊戲,已經紅了一段時間了。

在遊戲中,不同的植物可能相互作用,產生類似「合體技」的功能。這題的主要目標就是探討如何安排這些植物才能達到最大的攻擊力。為了簡化問題,我們只考慮只有一個殭屍以及田地只有一列的情況。

一列有$N$格的田地由左至右編號為$0,1,\dots,N-1$,每格田地的肥沃度是$a_i$。共有$Q$個關卡,而且每一個關卡都只有一個殭屍,並且進行的場地(也就是你能種植物的地方)是$N$格田地中的某一個區間$[L,R)$。而在每一關,你只有一個工具可以用:播種機。這是一個一次性道具,使用方法就是把他放在區間內最左邊的田地,之後他會開始往右開,並且在所經過的田地都種下一顆種子(含起點)。播種完(也就是超過編號R的田地)之後,還會直接輾過殭屍造成一定的傷害。而對於某個已種下種子且肥沃度是$a_i$的格子,過了一小段時間之後就會長出「特徵值」是$a_i$的植物。所種出的植物會發動合體技,產生一顆種子子彈。這顆種子子彈所造成的威力是$\sum k n_k^ 2$,其中$n_k$代表擁有特徵值$k$的植物個數。

對於給定的$Q$個關卡,請計算播種機造成的傷害(不含輾過去的傷害)。

Input Format

第一行有兩個正整數$N\leq 4\times 10^ 4, Q\leq 4\times 10^ 5$,分別代表田地大小以及關卡數目。
第二行有$N$個正整數$a_0,a_1,\dots,a_{N-1}\leq 10^ 9$,代表每格田地的肥沃度。
接下來的$Q$中每行會有兩個非負整數$L_i, R_i \leq N$($L_i<R_i$),分別代表關卡進行場地的左右界。

子任務(測資) 額外限制 分數
1 (0~4) $N,Q\leq 10^ 3$ 7
2 (5~10) $N\leq 10^ 4$ 19
3 (10~14) $Q\leq 10^ 5$ 37
4(15~19) 37

Output Format

對於每個關卡,請輸出造成的傷害值。由於答案很大,請將答案模1000000007後輸出。

Sample Input

4 2
0 2 2 3
0 3
2 4

Sample Output

8
5

Hints

本題的輸出輸入有點多。如果是使用C++式輸出輸入者,建議加入std::ios::sync_with_stdio(0), std::cin.tie(0);以及用'\n'替代std::endl增快輸出輸入速度。如果加入了std::ios::sync_with_stdio(0), std::cin.tie(0);,請勿同時使用C式以及C++式輸出輸入。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第五次模擬賽pA

Subtasks

For Testdata: 0 ~ 4, Score: 7
For Testdata: 5 ~ 9, Score: 19
For Testdata: 10 ~ 14, Score: 37
For Testdata: 15 ~ 19, Score: 37
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144
15 500 65536 262144
16 500 65536 262144
17 500 65536 262144
18 500 65536 262144
19 500 65536 262144