Chương trình cập nhật phần tử trong phạm vi cho trước bằng Python

Cho danh sách nums và danh sách các phép toán operations. Mỗi phép toán [L, R, X] nghĩa là tăng tất cả phần tử từ chỉ số L đến R (bao gồm cả hai) thêm X. Áp dụng tất cả phép toán và trả về danh sách cuối cùng.

Ví dụ: nums = [8, 4, 2, -9, 4], operations = [[0, 0, 3], [1, 3, 2], [2, 3, 5]] → [11, 6, 9, -2, 4].

Quy trình giải quyết (Kỹ thuật Difference Array / Sweep Line)

1. Tạo danh sách sự kiện events.
2. Với mỗi (l, r, inc), thêm (l, inc) và (r+1, -inc) vào events.
3. Sắp xếp events.
4. Duyệt qua chỉ số i của nums, giữ biến inc tích lũy và con trỏ ptr trên events.
5. Cập nhật nums[i] += inc.

Ví dụ mã nguồn

class Solution:
    def solve(self, nums, operations):
        events = []
        for l, r, inc in operations:
            events.append((l, inc))
            events.append((r + 1, -inc))
        events.sort()
        inc = 0
        ptr = 0
        for i in range(len(nums)):
            while ptr < len(events) and events[ptr][0] == i:
                inc += events[ptr][1]
                ptr += 1
            nums[i] += inc
        return nums

ob = Solution()
nums = [8, 4, 2, -9, 4]
operations = [[0, 0, 3], [1, 3, 2], [2, 3, 5]]
print(ob.solve(nums, operations))
# Output: [11, 6, 9, -2, 4]

Đầu vào

[8, 4, 2, -9, 4], [[0, 0, 3], [1, 3, 2], [2, 3, 5]]

Đầu ra

[11, 6, 9, -2, 4]