Tổng Lập Phương Cộng Dồn
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho dãy N số nguyên. Thao tác cộng x vào mọi phần tử của một đoạn, và truy vấn tổng lập phương a_l³ + ... + a_r³ modulo 10^9+7. Gợi ý: mỗi nút lưu đồng thời tổng bậc 1, bậc 2 và bậc 3.
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 a_l³ + ... + a_r³.
Dữ liệu ra
Với mỗi thao tác loại 2, in ra kết quả modulo 10^9+7 (không âm).
Ví dụ
| Input | Output |
|---|---|
| 5 4\n-5 8 5 -4 -4\n1 5 5 2\n1 1 5 1\n2 5 5\n1 5 5 6 | 1000000006 |
Giới hạn
- 1 ≤ N, Q ≤ 10^5
- |a_i|, |x| ≤ 10^9
Community Discussion