Hướng dẫn giải của [TS10 Tiền Giang 2025 - 2026] Tìm số lớn nhất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Dùng mảng hiệu ~diff~. Với cập nhật cộng ~M~ vào đoạn ~[u,v]~, thực hiện:
- ~diff[u] += M~.
- ~diff[v+1] -= M~.
Sau khi xử lý mọi cập nhật, lấy tổng tiền tố của ~diff~ để thu lại giá trị từng phần tử và lấy lớn nhất.
Độ phức tạp ~O(n+Q)~.
Bình luận