โปรแกรมหา XOR สูงสุดกับสมาชิกในอาร์เรย์สำหรับแต่ละคิวรีใน Python

มีอาร์เรย์ nums และคิวรี queries[i]=(xi, mi) คำตอบคิวรีที่ i = ค่า XOR สูงสุดของ xi กับสมาชิกใน nums ที่ ≤ mi (ถ้าไม่มีคืน -1)

ตัวอย่าง: nums=[0,1,2,3,4], queries=[[3,1],[1,3],[5,6]] ผลลัพธ์ [3,3,7]

วิธีแก้ปัญหา (Bitwise Trie + Offline)

1. เรียง nums และ queries ตาม limit
2. สร้าง prefix set ทีละบิต (31..0) เฉพาะค่า ≤ limit
3. Greedy เลือกบิตตรงข้ามกับ xi ถ้ามีใน prefix set

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

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))

อินพุต

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

เอาต์พุต

[3, 3, 7]