📖 Bài giảng & lời giải: đây là Bài tập 5 trong bài giảng Bài 37: Sparse Table, Lazy trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Một hội trường cho thuê trong $n$ ngày, ngày thứ $i$ còn $c_i$ chỗ trống. Lần lượt có $q$ yêu cầu, mỗi yêu cầu gồm ba số $l, r, k$: một đoàn $k$ người muốn ở từ ngày $l$ tới ngày $r$. Nếu mọi ngày từ $l$ tới $r$ đều còn ít nhất $k$ chỗ trống thì hội trường nhận đoàn (số chỗ trống của các ngày $l, \ldots, r$ cùng giảm $k$) và in YES; ngược lại từ chối đoàn (không có gì thay đổi) và in NO. Các yêu cầu được xử lý theo đúng thứ tự cho trong dữ liệu.

Dữ liệu vào

• Dòng 1: hai số nguyên $n, q$ ($1 \le n, q \le 10^5$).
• Dòng 2: $n$ số nguyên $c_1, c_2, \ldots, c_n$ ($0 \le c_i \le 10^9$).
• $q$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $l, r, k$ ($1 \le l \le r \le n$, $1 \le k \le 10^9$).

Kết quả

In $q$ dòng, dòng thứ $j$ là YES hoặc NO – kết quả của yêu cầu thứ $j$.

Sample Input

5 4
3 5 2 4 6
1 3 2
2 4 1
1 2 1
4 5 4

Sample Output

YES
NO
YES
YES