LC 100124. 找出强数对的最大异或值 II

https://leetcode.cn/problems/maximum-strong-pair-xor-ii/

这题大概思路是先求解y的特性，然后看看怎么快速地从符合条件的y里面找到异或最大值。

如果x<=y的话，那么可以得到 x <= y <= 2 * x. 所以我们只需要维护一个数据结构，这个数据结构里面都是 x <= y <= 2 * x 的值就行。这个用双指针就可以搞定。

接着就是这个数据结构了。要求接异或最大值的话，最直接的办法就是维护0,1的二叉树。鉴于其实nums[i]值的范围在[0,2^20)以内，所以这个二叉树可以使用树状数组来实现。

我们每次需要从这个数据结构里面删除和加入某些值的分支，并且更新分支上的值，这个数据结构就是线段树。

最后就是其实判断分支的方法可以写成许多的if-else, 但是也可以简化成下面这样的方式 `p = 2 * p + (1 - b)` 或者是 `p = 2 * p + b`. 代码看起来会更加简单。

这里使用的是 `(p-N)^x` 计算最后的xor结果，在搜索路径上我们其实也可以得到 xor 之后的值。

#!/usr/bin/env python
# coding:utf-8
# Copyright (C) dirlt

from typing import List


class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums.sort()
        MAXB = 20
        N = 1 << MAXB
        tree = [0] * (2 * N)

        def update(x, v):
            p = N + x
            tree[p] = v
            while p != 1:
                p2 = p // 2
                tree[p2] = tree[2 * p2] + tree[2 * p2 + 1]
                p = p2

        def search(x):
            p = 1
            if tree[p] == 0: return 0
            for i in reversed(range(MAXB)):
                b = (x >> i) & 0x1
                p2 = 2 * p + (1 - b)
                if not tree[p2]:
                    p2 = 2 * p + b
                p = p2
            assert (tree[p])
            return (p - N) ^ x

        j, k = 0, 0
        ans = 0
        for i in range(len(nums)):
            while j < i:
                update(nums[j], 0)
                j += 1
            while k < len(nums) and nums[k] <= 2 * nums[i]:
                update(nums[k], 1)
                k += 1
            r = search(nums[i])
            ans = max(ans, r)
        return ans