Cộng thêm vào một đoạn bằng mảng hiệu
Một mảng nhận liên tiếp các lệnh "cộng thêm v vào mọi phần tử trong đoạn [l, r]". Cách
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: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Một mảng nhận liên tiếp các lệnh "cộng thêm v vào mọi phần tử trong đoạn [l, r]". Cách ngây thơ là mỗi lệnh lại chạy một vòng lặp qua cả đoạn. Mảng hiệu làm điều ngược lại: mỗi lệnh chỉ ghi hai ô, rồi một lượt duyệt duy nhất ở cuối tái tạo lại toàn bộ mảng.
Yêu cầu
Cho mảng a gồm n số nguyên đánh số từ 1 đến n và u phép cập nhật. Mỗi phép cập nhật (l, r, v) cộng thêm v vào mọi phần tử a[l], a[l+1], ..., a[r]. Hãy in ra mảng sau khi áp dụng hết các phép cập nhật, theo đúng thứ tự từ vị trí 1 đến n.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. In đúng một dòng gồm n số nguyên, không in thêm chữ nào khác.
Input
- Dòng thứ nhất: số nguyên n là số phần tử (1 <= n <= 20).
- Dòng thứ hai: n số nguyên a[1] đến a[n], cách nhau bởi dấu cách (|a[i]| <= 10000).
- Dòng thứ ba: số nguyên u là số phép cập nhật (1 <= u <= 10).
- u dòng tiếp theo: mỗi dòng ba số nguyên l, r, v theo thứ tự đó, cách nhau bởi dấu
cách (1 <= l <= r <= n, -100 <= v <= 100).
Output
- Một dòng duy nhất chứa n số nguyên là mảng sau khi cập nhật, cách nhau đúng một dấu cách.
Ràng buộc
- 1 <= n <= 20, 1 <= u <= 10, |a[i]| <= 10000, -100 <= v <= 100.
- v có thể âm, nên phép cập nhật cũng có thể làm giá trị giảm xuống.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
5
0 0 0 0 0
2
1 3 5
2 4 3
Output
5 8 8 3 0
Ví dụ 2
Input
3
1 2 3
1
1 3 -1
Output
0 1 2
Giải thích
Với dữ liệu vào:
Sau lệnh đầu mảng là 5 5 5 0 0, sau lệnh thứ hai là 5 8 8 3 0, nên kết quả là:
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.
