Cấp Số Cộng Trên Đoạn

Buổi 28 — Segment Tree Lazy
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho dãy N số nguyên không âm. Thao tác 1 l r f d cộng vào a_l số f, vào a_{l+1} số f + d, vào a_{l+2} số f + 2d, ..., tức là cộng cấp số cộng vào đoạn [l, r]. Hãy trả lời tổng các đoạn, modulo 10^9+7.

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 f d: với mỗi i ∈ [l, r], cộng f + (i − l)·d vào a_i.
  • 2 l r: hỏi tổng a_l + ... + a_r.
Dữ liệu ra

Với mỗi thao tác loại 2, in ra tổng đoạn modulo 10^9+7.

Ví dụ
Input Output
5 4\n9 7 9 8 6\n1 5 5 4 8\n2 5 5\n2 2 5\n1 4 5 0 9 10\n34
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • 0 ≤ a_i, f, d ≤ 10^9
Draft saved