Tổng trọng số
Xem PDF
Điểm:
1100
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho mảng \(A\) gồm \(N\) số nguyên. Có \(Q\) truy vấn, mỗi truy vấn cung cấp hai chỉ số \(L\) và \(R\). Hãy tính tổng các phần tử trong đoạn từ \(L\) đến \(R\), nhưng với một quy tắc đặc biệt: Phần tử đầu tiên của đoạn (tại \(L\)) được nhân với \(1\), phần tử thứ hai (tại \(L+1\)) được nhân với \(2\), ..., phần tử cuối cùng (tại \(R\)) được nhân với \((R - L + 1)\).
Công thức cụ thể cho mỗi truy vấn \((L, R)\):
\[Ans = 1 \cdot A_L + 2 \cdot A_{L+1} + 3 \cdot A_{L+2} + \dots + (R - L + 1) \cdot A_R\]
\[Ans = \sum_{i=L}^{R} A_i \cdot (i - L + 1)\]
Input
- Dòng 1: Hai số nguyên \(N, Q\) (\(1 \le N, Q \le 2 \cdot 10^5\)).
- Dòng 2: \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(|A_i| \le 10^6\)).
- \(Q\) dòng tiếp theo: Mỗi dòng 2 số \(L, R\) (\(1 \le L \le R \le N\)).
Output
- Với mỗi truy vấn, in ra kết quả tìm được.
Example
Test 1
Input
5 2
1 2 3 4 5
1 3
2 4Output
14
20Note
- Truy vấn 1 (1 đến 3): Đoạn \(\{1, 2, 3\}\). Tính: \(1 \cdot 1 + 2 \cdot 2 + 3 \cdot 3 = 1 + 4 + 9 = 14\).
- Truy vấn 2 (2 đến 4): Đoạn \(\{2, 3, 4\}\). Tính: \(2 \cdot 1 + 3 \cdot 2 + 4 \cdot 3 = 2 + 6 + 12 = 20\).
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(N, Q \le 1000\).
- Subtask \(2\) (\(70\%\) số điểm): \(N, Q \le 2 \cdot 10^5\).
Bình luận (1)