TopCoder

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

User's AC Ratio

95.7% (22/23)

Submission's AC Ratio

27.8% (55/198)

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

No. Testdata Range Score
1 0~4 7
2 5~9 19
3 10~14 37
4 15~19 37

Testdata and Limits

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