โปรแกรมอัปเดตสมาชิกในช่วงที่กำหนดใน Python

สมมติว่าเรามีรายการตัวเลข nums และรายการออปเปอเรชัน แต่ละออปเปอเรชันมี 3 ฟิลด์ [L, R, X] หมายความว่าเราต้องเพิ่ม X ให้กับทุกสมาชิกจาก index L ถึง R (รวม) เราต้องนำออปเปอเรชันทั้งหมดไปใช้และคืนค่ารายการสุดท้าย

ตัวอย่าง: nums = [8, 4, 2, -9, 4], operations = [[0, 0, 3], [1, 3, 2], [2, 3, 5]] ผลลัพธ์คือ [11, 6, 9, -2, 4]

ขั้นตอนการแก้ปัญหา (Technique: Difference Array / Sweep Line)

1. สร้างลิสต์ events ว่าง
2. สำหรับแต่ละ (l, r, inc) ใน operations:
   • เพิ่ม (l, inc) เข้า events
   • เพิ่ม (r + 1, -inc) เข้า events
3. เรียงลำดับ events
4. กำหนด inc = 0, ptr = 0
5. สำหรับ i จาก 0 ถึง len(nums) - 1:
   • วนลูป while ptr < len(events) และ events[ptr][0] == i:
     • inc += events[ptr][1]
     • ptr += 1
   • nums[i] += inc
6. คืนค่า nums

ตัวอย่างโค้ด Python

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]

อินพุต / เอาต์พุต

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

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