Chương trình tìm số lượng quadruplet inverted inversions trong Python

Ví dụ: [3,4,7,6,5] → 5.

Giải thuật (Duyệt b từ trái sang, c từ phải sang + Binary Indexed Tree / Sorted List)

1. Duyệt c từ phải sang trái, duy trì sorted_ds (các nums[d] với d > c). ds_smaller_than_c[c] = số phần tử trong sorted_ds < nums[c].
2. Duyệt b từ trái sang phải, duy trì sorted_as (các nums[a] với a < b). as_smaller_than_b_sum = tổng số a thỏa mãn cho các b đã duyệt.
3. Khi ở b, quadruplet thêm vào = as_smaller_than_b_sum * ds_smaller_than_c[b+1].

Ví dụ minh họa

import bisect
MOD = 10**9 + 7

class Solution:
    def solve(self, nums):
        n = len(nums)
        if n < 4:
            return 0
        # Tính ds_smaller_than_c
        sorted_ds = [nums[-1]]
        ds_smaller_than_c = [0] * n
        for c in range(n - 2, -1, -1):
            ds_smaller_than_c[c] = bisect.bisect_right(sorted_ds, nums[c] - 1)
            bisect.insort(sorted_ds, nums[c])
        # Duyệt b
        sorted_as = [nums[0]]
        as_sum = 0
        ans = 0
        for b in range(1, n - 2):
            as_sum += bisect.bisect_right(sorted_as, nums[b] - 1)
            as_sum %= MOD
            bisect.insort(sorted_as, nums[b])
            ans = (ans + as_sum * ds_smaller_than_c[b + 1]) % MOD
        return ans

ob = Solution()
print(ob.solve([3, 4, 7, 6, 5]))  # Output: 5

Đầu vào / Đầu ra

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

Output: 5