Chương trình tìm XOR tối đa với phần tử từ mảng trong Python

Mô tả bài toán

Cho mảng nums và mảng truy vấn queries[i] = (xi, mi). Câu trả lời truy vấn i là max xi XOR nums[j] với nums[j] <= mi. Nếu không có phần tử nào <= mi, trả về -1.

Ví dụ

nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]] -> [3, 3, 7].

Giải thuật (Bitwise Trie + Offline)

1. Sắp xếp nums và queries theo limit.
2. Duyệt bit từ 31 xuống 0, xây dựng tập tiền tố prefixes của các số nums[j] >> k thỏa nums[j] <= limit.
3. Với mỗi truy vấn, cố gắng đặt bit kết quả = 1 nếu tồn tại tiền tố phù hợp.

Triển khai Python

def solve(nums, queries):
    m, n = len(nums), len(queries)
    queries = sorted(((i, x, limit) for i, (x, limit) in enumerate(queries)), key=lambda x: x[2])
    nums = sorted(nums)
    res = [0] * n
    for k in range(31, -1, -1):
        prefixes = set()
        j = 0
        for i, x, limit in queries:
            while j <= m - 1 and nums[j] <= limit:
                prefixes.add(nums[j] >> k)
                j += 1
            if not prefixes:
                res[i] = -1
            else:
                res[i] <<= 1
                target = res[i] ^ 1
                if (x >> k) ^ target in prefixes:
                    res[i] = target
    return res

nums = [0, 1, 2, 3, 4]
queries = [[3, 1], [1, 3], [5, 6]]
print(solve(nums, queries))

Đầu vào

[0,1,2,3,4], [[3,1],[1,3],[5,6]]

Đầu ra

[3, 3, 7]