Tổng Trọng Số Vị Trí

Buổi 28 — Segment Tree Lazy
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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
Draft saved