线性基求异或极值问题

for i from maxBit down to 0:
    if basis[i] != 0:
        for j from i-1 down to 0:
            if basis[i] 的第 j 位是 1:
                basis[i] ^= basis[j]   // 用低位基消去

class LinearBasis:
    def __init__(self, max_bit=60):
        # max_bit 是数字的最大二进制位数，一般 60 足够处理 10^18 以内的数
        self.basis = [0] * (max_bit + 1)   # 存储基向量，basis[i] 最高位为 i
        self.cnt = 0                       # 基中非零向量的个数
        self.zero = False                  # 标记能否异或出0（是否有线性相关）

    def insert(self, x):
        """向线性基中插入一个数，返回是否成功（不改变原有基）"""
        for i in range(len(self.basis)-1, -1, -1):
            if (x >> i) & 1:
                if self.basis[i] == 0:
                    self.basis[i] = x
                    self.cnt += 1
                    return True
                x ^= self.basis[i]
        # 如果 x 最后变成0，说明线性相关，可以异或出0
        self.zero = True
        return False

    def get_max(self):
        """求能异或出的最大值"""
        ans = 0
        for i in range(len(self.basis)-1, -1, -1):
            if (ans ^ self.basis[i]) > ans:    # 贪心：异或后变大就异或
                ans ^= self.basis[i]
        return ans

    def get_min(self, include_empty=False):
        """求最小值
           include_empty=True 时包括空集（结果为0）
           否则返回非空子集的最小值（即最小的非零基向量或0如果存在）"""
        if include_empty:
            return 0
        if self.zero:   # 存在线性相关，可以异或出0（非空子集）
            return 0
        # 否则找到最小的非零基向量
        for i in range(len(self.basis)):
            if self.basis[i] != 0:
                return self.basis[i]
        return 0   # 没有元素时返回0（但通常不会出现）

    def standardize(self):
        """将基化为标准形（阶梯形），使得每个基向量低位干净"""
        # 从高位到低位消去
        for i in range(len(self.basis)-1, -1, -1):
            if self.basis[i] == 0:
                continue
            for j in range(i-1, -1, -1):
                if (self.basis[i] >> j) & 1:
                    self.basis[i] ^= self.basis[j]
        # 收集非零基向量到列表 p，从小到大（最高位从小到大）
        self.p = []
        for i in range(len(self.basis)):
            if self.basis[i] != 0:
                self.p.append(self.basis[i])
        # 注意：此时 self.p 中元素是最高位递增的（因为 i 从小到大）
        # 如果要从大到小，可以 reverse，但为了第k小方便，用从小到大
        # 我们保留从小到大：p[0]最小，p[-1]最大

    def get_kth(self, k, zero_included=True):
        """求第k小（k从0开始），
           zero_included=True 时认为0是第0小，
           否则第0小是非零最小 """
        # 先标准化（若还未标准化）
        if not hasattr(self, 'p'):
            self.standardize()
        m = len(self.p)
        # 计算能表示的不同结果总数：2^m 个（包括0）
        # 如果 zero_included 为 False，并且可以异或出0，则实际上非0结果个数仍是2^m-1? 注意区分
        # 这里简化处理：默认 zero_included=True，即包括0。
        # 如果题目要求排除0，则检查 k 是否超过范围
        if zero_included:
            # 包括0时，第k小对应k
            total = 1 << m
            if k >= total:
                return -1   # 超出范围
            ans = 0
            # 注意 p 是从小到大（p[0]最小），那么k的二进制第0位对应p[0]
            for i in range(m):
                if (k >> i) & 1:
                    ans ^= self.p[i]
            return ans
        else:
            # 不包括0：那么第0小应该是第一个非0结果
            # 先判断能否得到0：如果 self.zero 为 True，则非空子集中有0；否则没有0
            can_zero = self.zero
            total = (1 << m) - (0 if can_zero else 0)  # 实际上有0时，非0结果数 = 2^m -1 (因为排除0)
            # 更严谨：非空子集结果数 = 2^m - (1 if can_zero else 0) ？不对，如果 can_zero 为真，那么0可以通过非空子集得到，所以非空结果包括0，但我们要排除0，所以总数减1
            # 但第k小（不包括0）的范围是0..(total-1)，其中total = 2^m - (1 if can_zero else 0)
            # 这比较复杂，建议统一用包括0的做法，然后根据题意转换k
            # 例如，题目要求第1小（非空最小），则调用 get_kth(1) 包括0，但得到的是第1小（包括0）即p[0]？
            # 实际上，如果包括0，第1小是p[0]（最小非零），所以直接取k=1即可（注意k从0开始，第1小对应k=1）
            # 更简单：我们只实现包括0的，调用时传入k=题目要求第几小- (0 if 包括0 else 1)
            pass

# 使用示例
if __name__ == "__main__":
    arr = [3, 5, 6]
    lb = LinearBasis()
    for x in arr:
        lb.insert(x)
    print("最大值:", lb.get_max())           # 6
    print("最小值（包括空集）:", lb.get_min(True))          # 0
    print("最小值（非空）:", lb.get_min(False))            # 3
    lb.standardize()
    print("标准基:", lb.p)                   #  [3,5] 或 [5,3]？取决于顺序，这里p从小到大是[3,5]
    print("第0小:", lb.get_kth(0))           # 0
    print("第1小:", lb.get_kth(1))           # 3
    print("第2小:", lb.get_kth(2))           # 5
    print("第3小:", lb.get_kth(3))           # 6