Snowdrop收藏著一整排可愛的gura玩偶。
每個玩偶都擁有獨特的能量，當她將它們依序排成一列時，這些能量會彼此產生「共鳴」。
Snowdrop 想知道，在某一段玩偶之間，能量會產生多大的共鳴值。
共鳴值的計算方式如下：
對於從第 L 個到第 R 個玩偶：
第 L 個玩偶的能量乘上 1，
第 L+1 個乘上 2，
依此類推，直到第 r 個玩偶乘上 R−L+1。
r(L,R) = aL × 1 + aL+1 × 2 + aL+2 × 3 + … + ar × (R-L+1)
給定 Snowdrop 收藏的 n 個玩偶能量值序列： (a₁, a₂, …, an)
接著會有 q 次詢問。 每次詢問會給出兩個整數 l 和 r， 請你幫 Snowdrop 計算從第 L 個到第 R 個玩偶之間產生的共鳴值。
第一行：一個整數 n，代表玩偶的數量。
第二行：n 個整數 a₁, a₂, …, an，分別表示每個玩偶的魔法能量值。
第三行：一個整數 q，代表詢問次數。
接下來的 q 行：每行包含兩個整數 L, R，代表 Snowdrop 想查詢的玩偶區間。
對於每個查詢，輸出一行，內容為該區間玩偶的共鳴值。
6 1 1 4 5 1 4 3 1 3 5 6 2 5
15 9 28
For the first query in the sample input, the answer should be a1 * 1 + a2 * 2 + a3 * 3 = 1 * 1 + 1 * 2 + 4 * 3 = 15. For the second query, the answer should be a5 * 1 + a6 * 2 = 1 * 1 + 2 * 4 = 9.
對於範例輸入中的第一個查詢，答案應為
a₁ × 1 + a₂ × 2 + a₃ × 3 = 1 × 1 + 1 × 2 + 4 × 3 = 15。
對於第二個查詢，答案應為
a₅ × 1 + a₆ × 2 = 1 × 1 + 2 × 4 = 9。
範圍:
1 ≤ n ≤ 105 0 ≤ ai < 232, i = 1, 2, ..., n
1 ≤ q ≤ 106
1 ≤ l ≤ r ≤ n
子任務:
Testcase 0~2: n <= 1000 , q ≤ 105
Testcase 3:無額外限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||