Gán Hay Cộng

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

Kho hàng có N ngăn, ngăn i chứa a_i sản phẩm. Quản lý có thể nhập thêm x sản phẩm vào mọi ngăn trong một dãy, hoặc kiểm kê lại và đặt số sản phẩm của mọi ngăn trong dãy đúng bằng x. Hãy trả lời tổng số sản phẩm trong các dãy ngă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 x: gán a_i = x 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.

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