Sơn Lại Hàng Rào

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

Hàng rào có N tấm ván, tấm i có giá trị thẩm mỹ a_i. Thợ sơn có thể sơn lại một dãy ván liên tiếp để tất cả chúng có cùng giá trị thẩm mỹ x. Hãy trả lời tổng giá trị thẩm mỹ của các đoạn vá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: gán a_i = x với mọi i ∈ [l, r].
  • 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.

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