每个查询的最大异或值

记牢两句话:第一,每次答案 k = xs 异或 mask,其中 xs 是当前总异或、mask 是 maximumBit 位全 1;第二,删掉末尾那个数 v,只要 xs 异或 v 就能同步更新总异或。下面每一帧都在套这两条。

阶段一 · 先备好 mask：先把 mask 定下来。maximumBit 是 3,mask 就是 2 的 3 次方减 1,等于 7,二进制是 111,三位全是 1,它是 k 能取到的最大值,也是每次能顶到的最大异或值。舞台上这排是 nums = [2, 3, 4, 7],接下来先把它们全部异或起来,得到初始的总异或 xs。

阶段一 · 异或进 nums[0]：把 nums[0] = 2 异或进总异或。上一步 xs 是 0,二进制 000,和 2 的二进制 010 逐位比较,同位相同得 0、不同得 1,结果是 010,也就是 2。现在 xs 更新成 2。

阶段一 · 异或进 nums[1]：把 nums[1] = 3 异或进总异或。上一步 xs 是 2,二进制 010,和 3 的二进制 011 逐位比较,同位相同得 0、不同得 1,结果是 001,也就是 1。现在 xs 更新成 1。

阶段一 · 异或进 nums[2]：把 nums[2] = 4 异或进总异或。上一步 xs 是 1,二进制 001,和 4 的二进制 100 逐位比较,同位相同得 0、不同得 1,结果是 101,也就是 5。现在 xs 更新成 5。

阶段一 · 异或进 nums[3]：把 nums[3] = 7 异或进总异或。上一步 xs 是 5,二进制 101,和 7 的二进制 111 逐位比较,同位相同得 0、不同得 1,结果是 010,也就是 2。现在 xs 更新成 2。

阶段一完成 · 总异或就绪：四个数全异或完了,总异或 xs = 2,二进制 010。手边现在有两样东西:总异或 xs = 2,还有 mask = 7。下面开始逐个查询,每次都用这两样算出答案 k。

核心 · 为什么取 k = xs ⊕ mask：再把核心想清楚。我们要让 xs 异或 k 最大,最大能有多大?每一位都变成 1,就是 mask。想让某一位变 1,k 在那一位就取和 xs 相反的值,合起来 k 就是 xs 异或 mask。代回去,xs 异或 k 等于 xs 异或 xs 异或 mask,前两个 xs 抵消,只剩 mask,正好顶满。而且这样的 k 一定在 0 到 mask 之间,是合法的选择。所以每次查询的答案就是 k = xs 异或 mask。

查询 0 · 看当前状态：第 0 次查询。舞台上灰掉的是前几轮已经删掉的,还亮着的这 4 个数就是当前数组,它们的总异或 xs = 2,二进制 010。下一步用 xs 和 mask 算这次的 k。

查询 0 · 算出 k = 5：套公式,k = xs 异或 mask = 2 异或 7。二进制是 010 异或 111,逐位取反得到 101,也就是 5。验证一下,把这个 k 和 xs 异或回去,010 异或 101 等于 111,正好是 mask,顶满了。把 5 记进答案,现在是 [5]。

查询 0 · 删末尾更新 xs：这次查询做完,按题意删掉末尾元素 nums[3] = 7,标红的就是它。总异或不用重算,异或自己是自己的逆运算,把 xs 异或这个 7 就等于把它剔出去:2 异或 7 等于 5。数组缩短一格,带着新的 xs = 5 进下一次查询。

查询 1 · 看当前状态：第 1 次查询。舞台上灰掉的是前几轮已经删掉的,还亮着的这 3 个数就是当前数组,它们的总异或 xs = 5,二进制 101。下一步用 xs 和 mask 算这次的 k。

查询 1 · 算出 k = 2：套公式,k = xs 异或 mask = 5 异或 7。二进制是 101 异或 111,逐位取反得到 010,也就是 2。验证一下,把这个 k 和 xs 异或回去,101 异或 010 等于 111,正好是 mask,顶满了。把 2 记进答案,现在是 [5、2]。

查询 1 · 删末尾更新 xs：这次查询做完,按题意删掉末尾元素 nums[2] = 4,标红的就是它。总异或不用重算,异或自己是自己的逆运算,把 xs 异或这个 4 就等于把它剔出去:5 异或 4 等于 1。数组缩短一格,带着新的 xs = 1 进下一次查询。

查询 2 · 看当前状态：第 2 次查询。舞台上灰掉的是前几轮已经删掉的,还亮着的这 2 个数就是当前数组,它们的总异或 xs = 1,二进制 001。下一步用 xs 和 mask 算这次的 k。

查询 2 · 算出 k = 6：套公式,k = xs 异或 mask = 1 异或 7。二进制是 001 异或 111,逐位取反得到 110,也就是 6。验证一下,把这个 k 和 xs 异或回去,001 异或 110 等于 111,正好是 mask,顶满了。把 6 记进答案,现在是 [5、2、6]。

查询 2 · 删末尾更新 xs：这次查询做完,按题意删掉末尾元素 nums[1] = 3,标红的就是它。总异或不用重算,异或自己是自己的逆运算,把 xs 异或这个 3 就等于把它剔出去:1 异或 3 等于 2。数组缩短一格,带着新的 xs = 2 进下一次查询。

查询 3 · 看当前状态：第 3 次查询。舞台上灰掉的是前几轮已经删掉的,还亮着的这 1 个数就是当前数组,它们的总异或 xs = 2,二进制 010。下一步用 xs 和 mask 算这次的 k。

查询 3 · 算出 k = 5：套公式,k = xs 异或 mask = 2 异或 7。二进制是 010 异或 111,逐位取反得到 101,也就是 5。验证一下,把这个 k 和 xs 异或回去,010 异或 101 等于 111,正好是 mask,顶满了。把 5 记进答案,现在是 [5、2、6、5]。

查询 3 · 删末尾更新 xs：这次查询做完,按题意删掉末尾元素 nums[0] = 2,标红的就是它。总异或不用重算,异或自己是自己的逆运算,把 xs 异或这个 2 就等于把它剔出去:2 异或 2 等于 0。数组清空,xs = 0,所有查询都答完了。

完成 · 答案 [5, 2, 6, 5]：四次查询都答完了,回放一遍:每次都是拿当轮的总异或 xs 异或 mask 得到 k,分别是 5、2、6、5,删末尾就顺手把那个数从 xs 里异或掉。最终答案数组是 [5、2、6、5]。总异或只算一次,之后每次查询都是常数时间。

边界先想清:元素是 0 时 k 直接取 mask、元素等于 xs 时 k 可能是 0、有重复值时靠异或抵消照样正确。

面试重点:最大值恒为 mask 是因为 k 自由到能逐位翻 1、删元素靠异或自反 O(1) 维护、换成删开头也只是改异或对象。