Cộng Dồn Và Hạ Trần

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

Một dãy N cảm biến, cảm biến i đang đo a_i. Hệ thống có hai loại lệnh trên một đoạn: cộng thêm x vào mọi giá trị (x có thể âm), và 'hạ trần': mọi giá trị lớn hơn x bị đặt lại đúng bằng x. Hãy trả lời tổng và giá trị lớn nhất của các đoạn được hỏi. Gợi ý: Segment Tree Beats với hai tag cộng (cho phần tử lớn nhất và cho các phần tử còn lại).

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: với mọi i ∈ [l, r]: a_i = min(a_i, x).
  • 3 l r: hỏi a_l + ... + a_r.
  • 4 l r: hỏi max(a_l..a_r).
Dữ liệu ra

Với mỗi thao tác loại 3 hoặc 4, in ra kết quả tương ứng.

Ví dụ
Input Output
5 4\n-1 -4 7 2 -9\n4 3 4\n4 5 5\n1 3 4 -6\n2 1 1 -1 7\n-9
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • |a_i| ≤ 10^9; |x| ≤ 10^4 cho thao tác loại 1; |x| ≤ 10^9 cho thao tác loại 2
Draft saved