Nhân Rồi Cộng Đoạn

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

Cho dãy N số nguyên không âm. Có thể nhân mọi phần tử của một đoạn với x, hoặc cộng x vào mọi phần tử của một đoạn, và hỏi tổng một đoạn. Mọi kết quả lấy modulo 998244353.

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: nhân a_i với x với mọi i ∈ [l, r].
  • 2 l r x: cộng x vào a_i với mọi i ∈ [l, r].
  • 3 l r: hỏi tổng a_l + ... + a_r.
Dữ liệu ra

Với mỗi thao tác loại 3, in ra tổng đoạn modulo 998244353.

Ví dụ
Input Output
5 4\n0 0 5 0 4\n3 3 5\n2 3 5 6\n2 4 4 9\n1 4 4 8 9
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • 0 ≤ a_i, x ≤ 10^9
Draft saved