โปรแกรมหา Inverted Inversions ใน Python

ตัวอย่าง

Input: [3, 4, 7, 6, 5]

Output: 5

Quadruplets: (3,4,7,6), (3,4,6,5), (3,4,7,5), (3,7,6,5), (4,7,6,5)

แนวทางแก้ปัญหา

Two-pass + Binary Indexed Tree / Sorted List:

1. Pass 1 (Right to Left): สำหรับแต่ละ c นับจำนวน d > c ที่ nums[d] < nums[c] → ds_smaller_than_c[c]
2. Pass 2 (Left to Right): สำหรับแต่ละ b สะสมจำนวน a < b ที่ nums[a] < nums[b] → as_smaller_than_b_sum
3. รวม: Σ as_smaller_than_b_sum[b] × ds_smaller_than_c[b+1]

การใช้งาน (Python)

import bisect

MOD = 10**9 + 7

class Solution:
    def solve(self, nums):
        n = len(nums)
        if n < 4:
            return 0
        
        # Pass 1: Right to Left - count d for each c
        sorted_ds = [nums[-1]]
        ds_smaller = [0] * n
        
        for c in range(n - 2, -1, -1):
            # จำนวน d ที่ nums[d] < nums[c]
            ds_smaller[c] = bisect.bisect_left(sorted_ds, nums[c])
            bisect.insort(sorted_ds, nums[c])
        
        # Pass 2: Left to Right - accumulate a for each b
        sorted_as = [nums[0]]
        as_sum = 0
        ans = 0
        
        for b in range(1, n - 2):
            # เพิ่ม a ใหม่เข้า sorted_as
            as_sum += bisect.bisect_left(sorted_as, nums[b])
            as_sum %= MOD
            bisect.insort(sorted_as, nums[b])
            
            # คูณกับ ds_smaller ของ c = b+1
            ans = (ans + as_sum * ds_smaller[b + 1]) % MOD
        
        return ans

# ทดสอบ
ob = Solution()
print(ob.solve([3, 4, 7, 6, 5]))  # Output: 5

ความซับซ้อน

• Time Complexity: O(N log N) (bisect บน list)
• Space Complexity: O(N)

หมายเหตุ: bisect.insort บน list เป็น O(N) ทำให้รวม O(N²) สำหรับ N ใหญ่ควรใช้ Fenwick Tree