Mảng hiệu số: Cập nhật đoạn O(1) trên mảng 1D và 2D
Ban đầu có một dãy gồm N số 0 được đánh số từ 1 đến N. Bạn cần thực hiện Q thao tác cập nhật: mỗi thao tác cộng thêm V vào tất cả các phần tử từ chỉ số L đến R (1 ≤ L ≤ R ≤ N).
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: prefix sum, arrays.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu cấu trúc mảng hiệu số (Difference Array) D[i] = A[i] - A[i-1].
- Thao tác cộng giá trị V vào đoạn [L, R] trong O(1): D[L] += V và D[R+1] -= V.
- Khôi phục mảng ban đầu bằng mảng cộng dồn trong O(N).
Mô tả bài toán
Ban đầu có một dãy gồm N số 0 được đánh số từ 1 đến N. Bạn cần thực hiện Q thao tác cập nhật: mỗi thao tác cộng thêm V vào tất cả các phần tử từ chỉ số L đến R (1 ≤ L ≤ R ≤ N). Sau khi hoàn thành tất cả Q thao tác, hãy in ra toàn bộ dãy số.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
- Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
- Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng 1: Gồm 2 số nguyên N, Q (1 ≤ N, Q ≤ 105).
- Q dòng tiếp theo: Mỗi dòng gồm 3 số nguyên L, R, V (1 ≤ L ≤ R ≤ N, -109 ≤ V ≤ 109).
Output
- In ra N số nguyên của dãy sau khi thực hiện xong tất cả Q thao tác, cách nhau bởi một khoảng trắng.
Ràng buộc
- 1 ≤ N, Q ≤ 105.
- Thời gian: 1000ms. Bộ nhớ: 256MB.
Ví dụ 1
Input
5 3
1 3 10
2 5 5
3 4 -2
Output
10 15 13 3 5
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
