Phân Đoạn Log Đặt Món ShopeeFood

Mô tả

Bạn mở ứng dụng ShopeeFood xem lại lịch sử đặt món trong tháng vừa rồi. Hệ thống lưu một danh sách chi_phi theo đúng thứ tự thời gian nhận đơn — phần tử đầu tiên là đơn sớm nhất, phần tử cuối cùng là đơn trễ nhất. Để tiện kiểm tra chi tiêu, bạn chia lịch sử thành nhiều đoạn liên tiếp bằng các mốc cắt moc. Với dãy chi_phi gồm n phần tử và danh sách k mốc moc[0] < moc[1] < ... < moc[k-1], đoạn thứ i chạy từ chỉ số bắt đầu start_i đến chỉ số kết thúc end_i (lấy cả hai đầu) theo quy tắc:

• Đoạn 0: từ 0 đến moc[0].
• Đoạn i (với 1 <= i <= k-1): từ moc[i-1] + 1 đến moc[i].
• Đoạn cuối: từ moc[k-1] + 1 đến n-1. Nhiệm vụ của bạn: tính tổng chi phí từng đoạn, trả về một danh sách gồm đúng k + 1 tổng theo đúng thứ tự đoạn từ sớm đến muộn.

Đầu vào

• chi_phi: danh sách số nguyên dương, độ dài n (1 <= n <= 10^5).
• moc: danh sách số nguyên không âm đã sắp xếp tăng nghiêm ngặt, độ dài k (1 <= k <= 10^5).

Đầu ra

• Trả về danh sách gồm k + 1 số nguyên, mỗi số là tổng các phần tử trong đoạn tương ứng.

Ràng buộc

• 1 <= n <= 10^5, 1 <= k <= 10^5.
• 1 <= chi_phi[i] <= 10^4.
• 0 <= moc[0], moc[k-1] <= n - 1.
• Các mốc tăng nghiêm ngặt: moc[0] < moc[1] < ... < moc[k-1].
• Tổng tất cả phần tử không vượt 10^9.

Ví dụ

Ví dụ 1:

• Đầu vào: chi_phi = [30000, 55000, 22000, 80000, 15000], moc = [1, 3]
• Đầu ra: [85000, 102000, 15000]
• Giải thích: Đoạn 0 chạy từ chỉ số 0 đến 1, tổng 30000 + 55000 = 85000. Đoạn 1 chạy từ chỉ số 2 đến 3, tổng 22000 + 80000 = 102000. Đoạn 2 chạy từ chỉ số 4 đến 4, tổng đúng 15000.

Ví dụ 2:

• Đầu vào: chi_phi = [12000, 45000, 67000], moc = [0]
• Đầu ra: [12000, 112000]
• Giải thích: Đoạn 0 chỉ gồm phần tử đầu tiên 12000. Đoạn 1 gồm hai phần tử còn lại 45000 + 67000 = 112000.