Tổng Trọng Số Vị Trí
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho dãy N số nguyên. Giá trị của một đoạn [l, r] được định nghĩa là tổng của i · a_i với i chạy từ l đến r (trọng số là chỉ số vị trí trong toàn dãy). Hãy hỗ trợ cộng một giá trị vào cả một đoạn và tính giá trị của một đoạn.
Dữ liệu vào
Dòng đầu chứa hai số nguyên N và Q. Dòng thứ hai chứa N số nguyên a_1..a_N. Q dòng tiếp theo, mỗi dòng là một thao tác:
1 l r x: cộng x vào a_l..a_r.2 l r: hỏi l·a_l + (l+1)·a_{l+1} + ... + r·a_r.
Dữ liệu ra
Với mỗi thao tác loại 2, in ra giá trị của đoạn (đảm bảo vừa trong số nguyên 64 bit có dấu).
Ví dụ
| Input | Output |
|---|---|
| 5 4\n4 -4 3 3 1\n1 2 2 1\n2 1 3\n1 1 1 8\n1 3 5 3 | 7 |
Giới hạn
- 1 ≤ N, Q ≤ 10^5
- |a_i|, |x| ≤ 1000
Community Discussion