Đếm Kiện Cỏ

Lời giải: Đếm Kiện Cỏ

Hướng tiếp cận

Segment tree với lazy propagation hỗ trợ ba thao tác: cộng đoạn, truy vấn min đoạn, truy vấn tổng đoạn.

Nhận xét quan trọng

• Ba thao tác cần hỗ trợ đồng thời: range-add, range-min, range-sum.
• Mỗi nút segment tree lưu: min_val, sum, lazy (giá trị cộng thêm chưa đẩy xuống).
• Khi push-down lazy: min[con] += lazy, sum[con] += lazy * size[con], lazy[con] += lazy.

Thuật toán

1. Xây dựng segment tree từ dãy ban đầu.
2. Với truy vấn P A B C: range-add $C$ lên đoạn $[A,B]$.
3. Với truy vấn M A B: range-min trên đoạn $[A,B]$.
4. Với truy vấn S A B: range-sum trên đoạn $[A,B]$.

Độ phức tạp

• Thời gian: $O((N+Q)\log N)$
• Bộ nhớ: $O(N)$