你玩過植物大戰殭屍嗎?
這是一款用植物打趴殭屍的熱門遊戲,已經紅了一段時間了。
在遊戲中,不同的植物可能相互作用,產生類似「合體技」的功能。這題的主要目標就是探討如何安排這些植物才能達到最大的攻擊力。為了簡化問題,我們只考慮只有一個殭屍以及田地只有一列的情況。
一列有$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$個關卡,請計算播種機造成的傷害(不含輾過去的傷害)。
第一行有兩個正整數$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\leq 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 |
對於每個關卡,請輸出造成的傷害值。由於答案很大,請將答案模1000000007後輸出。
本題的輸出輸入有點多。如果是使用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 set / Description by Paupière
建國中學105學年度校內第五次模擬賽pA
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 7 |
2 | 5~9 | 19 |
3 | 10~14 | 37 |
4 | 15~19 | 37 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
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 |