位运算贪心构造#

位运算贪心构造的核心，在于利用二进制权重的指数级分布特性进行确定性决策。这类题目主要分为两种题型。第一种涉及 元素修改或重组操作 ，其求解关键是从动态操作中抽象出静态的 固有贡献 。题目提供的操作往往具有极强的方向性与不可逆性。例如，若操作为将元素 $a_i$ 与常数 $x$ 执行按位与（AND）运算，我们必须敏锐识别出位权空间的 不可触达区域：如果常数 $x$ 的某位为 $1$ ，则该位在操作扰动下将始终保持初始状态，无法被实质性改变。这种由 算子属性 决定的硬性约束，就是构造时必须预先锁定的 底层素材 。

在识别并锁定固有贡献后，接下来的决策逻辑往往紧跟着针对剩余空间的 高位贪心 。由于固有贡献属于无法更改的既定事实，我们应将其视为决策背景，而将贪心策略集中于那些 尚未被约束锁定、仍具备操作自由度 的位信息上。基于 $2^i > \sum_{j=0}^{i-1} 2^j$ 的位权特性，高位 $1$ 的价值严格大于低位总和。因此，在排除固有贡献的干扰后，我们必须将剩余位资源视为最稀缺资产，通过 高位决策 将其优先分配给能产生最大边际收益的位。这种在自由空间内实现的 位权压制 ，确保了我们在不触碰硬性约束的前提下，实现对全局目标函数上限的精准控制。

第二种题型则涉及 不带修改的操作 ，通常要求从既定数组中选数以构造特定数值，其核心在于应用 高位贪心过滤机制 。由于无法改变元素的内部位结构，决策过程被抽象为一种逐位的 存亡筛选 。以 子集最大 OR 为例，利用其 只增不减 的特性，贪心策略通常趋于全集累加，以纳入所有可能的位贡献。而在处理 子集最大 AND 时，基于其 只减不增 的单调性，决策演变为严密的 排除法：从最高位向低位逐一审视，若当前位为 $1$ 的元素集合足以支撑目标需求，则果断剔除在该位为 $0$ 的所有干扰元素。这种单向且不可逆的决策路径，利用高位结果为低位划定了更精确的搜索边界。

然而，当这种基于单调性的高位决策逻辑碰撞上 异或（XOR）运算 时，情况会发生质的变化。子集最大 XOR 问题无法简单地通过贡献重组或存亡过滤来解决。异或运算相同为 $0$ 且不同为 $1$ 的 自反特性 ，彻底破坏了数值增长的单调性。引入一个新元素可能会让原本已经确立的高位 $1$ 瞬间塌陷为 $0$ 。这种不确定性使得常规的贪心策略失效，迫使我们寻找更深层的 代数结构 来支撑决策。

最大异或乘积#

题目链接

12 5 4

98

6 7 5

930

1 6 3

12

题目要点解析#

本题要求在 $0 \leq x < 2^n$ 的范围内选择一个整数 $x$ ，使得 $(a \oplus x)(b \oplus x)$ 取得最大值。由于 $x$ 仅影响最低 $n$ 位，因此问题天然适合采用逐位分析的方法。对于位运算题目而言，常见的处理方式是拆位分析 ，因为按位运算本质上是逐位独立定义的。当我们决定采用拆位思路时，首先应当思考是否可以通过贪心提前确定某些位的操作，从而将问题规模逐步缩减。这种 “先确认显然最优的局部决策” 的思考方式，往往能够显著简化整体结构。

我们引入两个变量：

问题等价于最大化：

为了理解如何选择 $x$ ，我们从每一位出发分析 $a_i$ 与 $b_i$ 的关系：

• 当某一位满足 $a_i = b_i = 1$ 时，如果令 $x_i = 1$ ，则该位在 $A$ 与 $B$ 中都会变为 $0$ ；若令 $x_i = 0$ ，则保持为 $1$ 。显然，同时减少两个 $1$ 会降低乘积，因此这一位的最优策略是保持不变，即令 $x_i = 0$ 。

• 当某一位满足 $a_i = b_i = 0$ 时，如果令 $x_i = 1$ ，则该位在 $A$ 与 $B$ 中都会变为 $1$ ；若令 $x_i = 0$ ，则保持为 $0$ 。显然，同时增加两个 $1$ 会提升乘积，因此这一位的最优策略是保持不变，即令 $x_i = 1$ 。

经过上述两类情况的分析后，可以发现这些位的贡献已经完全确定，它们构成了一个不可改变的 “固定部分” 。真正影响优化结构的，是那些满足 $a_i \ne b_i$ 的位。在这些不同位上，若某位原本是 $a_i = 1, b_i = 0$ ，则当 $x_i = 0$ 时保持原状，当 $x_i = 1$ 时二者交换。因此，在这些位上，$x$ 的作用本质上是决定该位权值分配给 $A$ 还是 $B$ 。需要注意的是，无论如何分配，该位的权值 $2^i$ 总是存在于两者之一，因此这些位上的总权值是固定的，只是可以在两数之间重新分配。

设固定部分分别为 $C_A$ 与 $C_B$ ，所有不同位的权值总和为 $T$ 。则可以写成：

其中 $x$ 表示分配给 $A$ 的那部分权值。于是乘积为：

这是一个关于 $x$ 的二次函数。将其展开可以得到负的二次项系数，因此函数开口向下，存在唯一最大值。根据二次函数的基本性质可知，在总资源 $T$ 固定的情况下，当两数尽可能接近时，乘积达到最大。因此，最优策略是在可交换位上尽量平衡两数的大小。由于二进制数中高位权重大于低位，在具体实现时应当从高位到低位进行贪心决策，每当遇到一个可以分配的位，就优先将其分配给当前数值较小的一方，从而保持两数尽可能接近。

1
# include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

数组末尾最小值#

题目链接

3 4

6

2 7

15

题目要点解析#

本题依旧是一道典型的位运算构造问题，因此自然应当从拆位的角度进行分析。对于位运算题目，我们通常优先考虑逐位拆解，并结合贪心思想，尽可能先确定那些可以直接确定的 “固定贡献” ，从而将问题转化为剩余部分的结构优化。

题目要求构造一个严格递增的正整数数组 nums ，并满足所有元素的按位与结果等于 $x$ 。设数组为：

并要求：

按位与运算的性质决定了：某一位最终为 $1$ ，当且仅当 所有数在该位上都为 $1$ 。因此，如果 $x$ 的某一位是 $1$ ，那么数组中每一个元素在这一位上都必须是 $1$ 。这些位是完全被强制确定的，不存在任何选择空间。接下来考虑 $x$ 中为 $0$ 的位。对于这些位，只需保证在所有元素中至少有一个数在该位上为 $0$ ，即可保证最终按位与结果为 $0$ 。但由于我们希望数组严格递增且最后一个数尽量小，因此最优策略是尽量以最小幅度递增构造数组。

关键观察在于，既然所有数都必须包含 $x$ 的 $1$ 位，那么数组中的每个元素都可以写成：

其中 $y_i$ 只在 $x$ 为 $0$ 的位上可以自由取值。于是问题转化为：构造一个严格递增的序列 $y_0 < y_1 < \cdots < y_{n-1}$ ，并使得最终的 $nums_{n-1}$ 最小。

为了让 $nums_{n-1}$ 尽可能小，就应当让 $y_i$ 本身尽可能小且按最小步长递增。显然，最优构造方式是令：

但需要注意的是，这里的 $i$ 不是直接填入原数，而是将 $i$ 的二进制表示嵌入到 $x$ 为 $0$ 的那些位中。也就是说，我们将自然数序列 $0, 1, 2, 3, \dots, n-1$ 的二进制表示依次填入 $x$ 为 $0$ 的位置上，从低位到高位对应填充。

这样构造得到的序列天然严格递增，同时保证所有元素都包含 $x$ 的固定 $1$ 位，因此按位与结果恰好为 $x$ 。由于我们使用的是从 $0$ 开始的最小连续整数序列，因此最终得到的 $nums_{n-1}$ 也是所有合法构造中的最小值。

1
# include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

平方和最大操作#

题目链接

4 2
2 6 5 8

261

4 3
4 5 4 7

90

题目要点解析#

这道题依然是一类典型的位运算重排问题，因此自然应当从拆位分析入手。对于涉及 AND、OR 之类按位操作的题目，我们通常优先逐位研究其变化规律，寻找是否存在守恒量或固定贡献。一旦发现某种 “不可改变的结构” ，问题往往就会从复杂的操作模拟，转化为更本质的资源分配问题。

题目给定的操作为：任选两个数 $a, b$ ，执行：

为了理解其本质，我们只需考察单个位上的变化情况。设某一位上两数分别为 $(x,y)$ 。如果是 $(0,0)$ 或 $(1,1)$ ，显然操作后不发生变化；如果是 $(0,1)$ ，按位与得到 $0$ ，按位或得到 $1$ ，结果仍为 $(0,1)$ ；只有在 $(1,0)$ 时，会被调整为 $(0,1)$ 。

从这四种情况可以看出一个核心事实：每一位上的 $1$ 的总数量保持不变。操作只是在不同元素之间 “转移” 该位上的 $1$ ，而不会创造或消灭 $1$ 。因此，设第 $b$ 位上最初共有 $cnt_b$个 $1$ ，那么无论如何操作，最终这一位上仍然有且仅有 $cnt_b$ 个 $1$ 。这一步实际上已经揭示了问题的本质：我们可以在数组元素之间自由重新分配每一位上的 $1$ ，但各个位的 $1$ 的总数是守恒的。于是原问题等价于——在每一位上拥有 $cnt_b$ 个权值为 $2^b$ 的资源，可以任意分配到各个元素中。

接下来考虑目标函数。我们最终要从数组中选出 $k$ 个元素，使得它们的平方和最大：

平方函数是严格凸函数，这意味着在总和一定的情况下，将数值集中在少数元素上，比平均分配能获得更大的平方和，也就是：

因此，既然每一位上的贡献可以自由分配，那么最优策略必然是尽可能把各个位上的 $1$ 叠加到同一批元素上，从而构造出尽可能大的数。具体实现时，可以按如下贪心思路进行：统计所有 $cnt_b$ ，然后重复 $k$ 轮构造。每一轮构造一个新的数，对于所有满足 $cnt_b > 0$ 的位，将对应的 $2^b$ 加入当前数，并令：

这样得到的第一个数最大，第二个数次大，以此类推。由于每一轮都尽可能收集所有剩余的高位贡献，数值会呈现逐层递减的结构，而平方和则因高度集中而被最大化。

1
# include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

最大异或和操作#

题目链接

3 2 4 6

7

1 2 3 9 2

11

题目要点解析#

这道题的关键在于先理解给定操作到底能做什么。题目允许我们进行如下操作：

注意到最外层是一个按位与运算，左边的 nums[i] 本身就相当于一个 “掩码” 。这意味着，无论我们怎样选择 $x$ ，运算结果都不可能在原本为 $0$ 的位上变成 $1$ 。换句话说，这个操作只能把某些 $1$ 变成 $0$ ，而不能凭空增加新的 $1$ 。再看中间的异或部分。由于 $x$ 可以是任意非负整数，因此 nums[i] ^ x 可以在每一位上自由控制翻转与否。结合外层的按位与，可以发现我们实际上可以 “选择性地关闭” nums[i] 中的任意若干个 $1$ 。也就是说，经过若干次操作之后，nums[i] 可以变成它的任意一个子集，但绝对不能增加新的 $1$ 。

因此，本题的本质就变成了：我们可以对每个元素，删除它的一些 $1$ 位，但不能新增 $1$ 位。最终目标是让整个数组的异或值最大。

接下来从异或的角度分析。一个整数的异或结果在某一位上为 $1$ ，当且仅当该位上所有元素中 $1$ 的个数为奇数。既然我们可以删除某些 $1$ ，那么在每一位上，我们唯一能做的事情就是减少 $1$ 的数量。为了让最终异或结果最大，我们希望在尽可能高的位上得到 $1$ 。而某一位能否最终为 $1$ ，取决于这一位在所有元素中是否 “至少出现过一次” 。如果某一位在原数组中从未出现过 $1$ ，那么由于我们不能增加 $1$ ，这一位最终必然为 $0$ 。

而如果某一位原本出现过至少一次 $1$ ，那么我们就可以通过删除多余的 $1$ ，使这一位的 $1$ 的总数变成奇数，从而保证最终异或结果在这一位为 $1$ 。因为只要这一位原本有至少一个 $1$ ，我们就可以保留一个、删除其余全部，使其数量为 $1$（奇数）。因此，对于每一位，只要原数组中存在至少一个元素在该位为 $1$ ，我们就一定可以让最终异或结果在这一位为 $1$ ；如果原本没有，则永远无法得到 $1$ 。

这说明最终答案恰好等于所有元素的按位或结果：

因为按位或正好表示 “每一位是否至少出现过一次 1” 。

综上所述，这道题虽然操作形式复杂，但本质上只是一个位运算性质的转化问题。操作只能删除 $1$ ，不能增加 $1$ ；而异或最大化只关心每一位是否能保留奇数个 $1$ 。最终答案就是原数组的按位或值，时间复杂度为 $O(n)$ 。

1
# include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

最短or路径问题#

题目链接

4 5
1 2 1
1 3 4
2 3 2
2 4 4
3 4 3

3

3 5
1 2 1
1 2 2
1 2 3
1 2 4
2 3 4

4

8 12
4 5 16691344
5 7 129642441
2 7 789275447
3 8 335307651
3 5 530163333
5 6 811293773
3 8 333712701
1 2 2909941
2 3 160265478
5 7 465414272
1 3 903373004
6 7 408299562

468549631

题目要点解析#

或位运算

异或数列博弈论#

题目链接

题目要点解析#

异或位运算

最大异或对构造#

题目链接

题目要点解析#

异或位运算

位运算和式变换#

在一些涉及 位运算的求和问题 中，直接按照题意枚举所有元素往往是不可行的，因为数据范围通常非常大。这时，一个非常常见的技巧是对表达式进行 和式变换（sum transformation）：将原本关于整数的运算，转化为 按位统计贡献 的形式。

其核心思想来源于位运算的 按位独立性 。例如在计算大量异或、与、或运算的和时，可以将问题拆解为：每一位对最终答案的贡献 。对于某一位 $k$ ，只需要统计在所有数中这一位为 $0$ 或 $1$ 的数量，然后计算能够使该位为 $1$ 的组合数量，再乘上对应的权值 $2^k$ 。这样就把一个复杂的双重求和问题，转化为对每一位进行一次简单计数。

例如在求解下面这个累加和：

我们可以对每一位 $k$ 单独计算贡献。如果 $1 \sim n$ 中该位为 $1$ 的数量为 $a$ ，为 $0$ 的数量为 $n-a$ ，而 $1 \sim m$ 中该位为 $1$ 的数量为 $b$ ，为 $0$ 的数量为 $m-b$ ，那么只有 0 与 1 配对 才会使该位异或结果为 $1$ ，因此该位的贡献数量为：

通过这种方式，原本需要枚举 $nm$ 个配对的问题，可以被转化为 按位统计 + 数学计数 的过程，复杂度通常只需要 $O(\log n)$ 或 $O(\log m)$ 。这种思路在许多位运算求和问题中都非常常见，是逐位拆解方法的重要应用场景。从更深层次来看，这种方法之所以成立，尤其在异或问题中表现突出，是因为 异或运算本质上等价于二进制下的模 2 加法（无进位加法）。在每一位上，其运算规则为：

因此，可以把整数看作由 $0/1$ 组成的二进制向量，而异或运算就是对这些向量进行 逐位的模 2 加法 。由于不存在进位，不同二进制位之间完全独立，这也使得 “按位统计贡献” 的和式变换方法在异或问题中具有天然优势。

在其他类似的问题中，我们还可以将 “寻找满足某种异或关系的数对” 转化为寻找对应的 目标值 。这种结构与经典的两数之和思想非常相似：在遍历数组时，可以用哈希表记录已经出现过的元素，并查询当前元素对应的目标值 $a_i \oplus x$ 是否存在。如果存在，我们就找到了一组满足条件的数对。

数组异或序列和#

题目链接

题目要点解析#

子段和的异或和#

题目链接

题目要点解析#

AOR相关性质#

按位与和按位或运算都具有非常明显的 单调结构 。按位与运算会使数值 单调不增：某一位一旦在某次运算中变为 $0$ ，之后再进行与运算时就不可能恢复为 $1$ 。因此，在只包含按位与操作的过程中，整体数值只会不断减小，很多较大的状态从一开始就不可能被达到。这一性质在区间问题、动态维护以及状态压缩中经常被利用，例如区间按位与的不同结果数量通常是非常有限的。

与之相对，按位或运算则具有 单调不减 的特征：某一位一旦变为 $1$ ，之后通常无法再恢复为 $0$ 。因此，在只包含按位或操作的过程中，数值会不断增大，状态变化也会逐渐趋于稳定。利用这一性质，可以快速判断某些状态是否可达，并且在许多问题中可以证明不同结果的数量是受限的，从而避免枚举所有可能的状态。

此外，按位与和按位或还具有 幂等性 ，即：

这意味着重复执行同样的操作不会产生新的结果。在某些操作序列问题中，这种性质会导致过程在有限步之后 收敛到稳定状态 ，从而使得原本需要大量模拟的过程可以被显著简化。

多数目子数组#

题目链接

1 0 2 0 1 2

3

5 7 1 3

1

题目要点解析#

这道题的核心在于理解按位与运算的单调性质。对于一段区间而言，随着参与按位与的元素个数增加，结果只会保持不变或变小，而不可能变大。换句话说，区间越长，其按位与的结果越不利于增大总和。因此，在考虑如何划分子数组时，应当先分析整个数组的整体按位与结果。

设整个数组的按位与为：

显然，任意子数组的按位与结果都不会小于 $T$ 。因为整体按位与已经包含了所有元素的约束，是能够达到的最小值。也就是说，所有合法划分的子数组得分之和，至少为若干个不小于 $T$ 的数之和。

如果 $T > 0$ ，那么问题立刻变得简单。因为无论如何划分，每个子数组的按位与结果都不小于 $T$ ，一旦拆分成多个子数组，得分之和就至少为：

显然会严格大于单个整体区间的得分 $T$ 。既然题目要求总得分最小，那么此时最优策略只能是不拆分数组，即整个数组作为一个子数组，答案为 $1$ 。

接下来考虑 $T = 0$ 的情况。既然整体按位与已经为 $0$ ，说明存在某些位在不同元素之间互相 “抵消” ，最终使得整段区间的按位与结果为零。由于按位与运算是单调递减的，我们希望尽可能多地构造出按位与为 $0$ 的子数组。因为一旦某个子数组的得分为 $0$ ，它对总和的贡献就是最小的。

因此，在 $T = 0$ 的情况下，我们的目标转化为：将数组划分为尽可能多的连续区间，使得每个区间的按位与结果为 $0$ 。这样总得分仍然为 $0$ ，同时子数组数量最多。具体实现时，可以从左到右维护一个当前区间的按位与值，初始设为一个全 $1$ 的掩码或直接从第一个元素开始累积。每次将当前元素与进来，当结果变为 $0$ 时，就立即在此处切断，计数加一，并重新开始下一段区间的累积。由于按位与只会变小，一旦为 $0$ 就不可能再恢复，因此此时切分是最优且贪心正确的。

综上，本题的关键在于先计算整体按位与，分情况讨论。当整体按位与大于 $0$ 时答案为 $1$ ；当整体按位与为 $0$ 时，通过贪心切分每一个前缀按位与首次变为 $0$ 的位置，可以得到最多的子数组数量。这种思路的本质是利用按位与的单调性，将问题转化为 “尽可能多地制造零贡献区间” 的结构化贪心问题。

1
# include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

按位或最大数组#

题目链接

1 0 2 1 3

3 3 2 2 1

1 2

2 1

题目要点解析#

这道题如果换成 “子数组最大累加和” ，我们往往只需要维护某种前缀或后缀的最优结构即可，因为加法具有可逆性和线性结构。但按位或运算并不具备这种性质，它是不可逆的，因此必须从按位或本身的结构特征入手分析。

首先注意按位或的单调性，设：

当我们固定 $i$ ，不断增大 $j$ 时，$A_{i,j}$ 只可能变大或保持不变，不可能变小。因为某一位一旦在或运算中被置为 $1$ ，之后就不可能再变回 $0$ 。因此对于每个起点 $i$ ，所谓 “最大按位或值” ，实际上就是扩展到数组末尾得到的值：

问题就转化为：对于每个 $i$ ，找到最小的 $j$ ，使得：

如果从每个 $i$ 暴力向右扩展，时间复杂度会达到 $O(n^2)$ 。但按位或还有一个更关键的性质：由于整数最多只有 $32$ 位，而每一位最多只会从 $0$ 变成 $1$ 一次，因此对于固定起点 $i$ ，随着 $j$ 的增加，$A_{i,j}$ 的不同取值不超过 $32$ 种。

换一个角度来看，我们从右向左动态维护 “所有后缀按位或结果” 。设当前处理到位置 $i$ ，我们知道从 $i+1$ 开始的所有不同的后缀或值。将 $nums[i]$ 与这些值分别进行一次或运算，再加上单独的 $nums[i]$ ，就得到了从 $i$ 开始的所有后缀或值。

这里有一个非常重要的细节：后缀按位或值在扩展过程中是单调不减的，因此生成的新或值序列也是单调的。由于单调性，相同的或值一定是连续出现的。换句话说，若在更新过程中产生了重复值，那么这些重复值必然是相邻的，可以在构造时直接去重。

因此在实现时，我们只需维护一个有序数组（或列表）表示不同的后缀或值。每次更新时按顺序计算新的或值序列，并在生成过程中去掉与前一个相同的值即可。由于总状态数不超过 $32$ 个，因此每一步的复杂度是常数级的。

在得到从 $i$ 开始的所有不同后缀或值后，最大值就是该列表中的最后一个元素。由于我们在维护时可以同时记录每个或值最远延伸到的下标，因此可以直接得到最短的 $j$ ，从而计算答案长度。

1
# include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

题目相关拓展#

如果把本题中的 “最大 OR 值” 改成与 “最大 XOR 值” ，那么问题结构会发生明显变化。设我们定义后缀异或和：

则任意区间 $[i, j]$ 的异或值可以表示为：

因此，如果我们希望在固定起点 $i$ 的情况下，使某个后缀子区间的异或值最大，本质上就是在所有可能的 $S_{j+1}$ 中，找到一个值，使得 $S_i \oplus S_{j+1}$ 最大。这就转化成了一个经典问题：给定一个数，在一组数中找到与它异或结果最大的数 。这正是 “最大异或对” 问题。

解决这类问题的标准做法是使用二进制字典树（Trie）。具体思路如下：

我们从右向左遍历数组，动态计算后缀异或和 $S_i$ 。在处理到位置 $i$ 时，Trie 中已经存储了所有 $S_{j}$（其中 $j > i$ ）。此时我们在 Trie 中查询一个数，使得与当前 $S_i$ 异或的结果最大。Trie 的构造方式是按二进制位从高位到低位插入。查询时，为了让异或结果最大，我们在每一位上尽量选择与当前位相反的分支（若存在）。这样贪心地从高位优先保证结果尽可能大，最终得到全局最优解。

由于整数最多 $32$ 位，每次插入和查询的复杂度都是 $O(32)$ ，整体时间复杂度为 $O(32n)$ ，可以视为线性。

最长优雅子数组#

题目链接

1 3 8 48 10

3

3 1 5 11 13

1

题目要点解析#

题目要求子数组中任意两个不同位置的元素按位与结果为 $0$ 。等价地说，任意两个数在二进制表示中不能在同一位上同时为 $1$ 。也就是说，这个子数组中的所有数字，在二进制层面上 $1$ 的位置必须两两互不重叠。

从这个条件可以立刻得到一个重要结论：一个优雅子数组的长度不会超过二进制位数上限。因为一个整数最多只有 $32$ 位（在本题数据范围内甚至不到 $32$ 位），而每一位最多只能被一个元素占用。如果两个元素在同一位上都有 $1$ ，那么它们的按位与一定不为 $0$ ，子数组就不合法。因此，一个优雅子数组的最大长度最多是 $32$ ，也就是 “每个数只贡献一个不同的 $1$ 位” 的极端情况。

这个上界非常关键。数组长度可以达到 $10^5$ ，但真正需要考虑的窗口长度最多只有 $32$ 。也就是说，对于每个起点，向右最多扩展 $32$ 步就可以确定该起点能形成的最长优雅子数组。最直接的做法是枚举左端点 $i$ ，然后从 $i$ 开始向右扩展窗口，维护当前窗口内所有元素的按位或值 mask 。当我们尝试加入一个新元素 nums[j] 时，只需要检查：

如果成立，说明没有任何位冲突，可以加入窗口，并更新：

一旦不成立，就停止扩展当前起点。由于窗口长度最多 $32$ ，每个起点最多检查 $32$ 次，总时间复杂度为 $O(32n)$ ，可以视为线性复杂度。

当然，也可以用更标准的滑动窗口写法。用双指针维护一个区间 [l, r) ，同时维护当前窗口的按位或值 mask 。当加入 nums[r] 时，如果产生冲突（ mask & nums[r] != 0 ），就不断移动左指针，并把 nums[l] 从 mask 中删除。由于窗口中每一位只会出现一次，删除操作可以通过下面这个公式来完成：

这样每个元素最多进窗口一次、出窗口一次，总复杂度同样是线性。

1
# include <bits/stdc++.h>
2
using namespace std;
3

4
int main(){
5

6
}

XOR相关性质#

与按位与、按位或不同，按位异或运算并不具备明显的单调性，因此很多问题往往无法通过简单的 “不断变大” 或 “不断变小” 的规律来进行分析。许多复杂的异或问题，如果只从数值变化的角度出发，往往难以找到清晰的思路。

不过，异或运算本身具有一些非常特殊的 代数结构性质 。如果一组数的整体异或结果为 $x$ ，其中某一部分的异或结果为 $y$ ，那么剩余部分的异或结果一定为 $x \oplus y$ 。这一性质来源于异或的抵消性与可逆性：

也就是说，在异或运算中，整体信息可以被自由拆分，任意一部分都可以通过整体结果与另一部分的结果反推出，这使得很多问题可以从 “整体与部分” 的关系入手进行分析。

这一性质在实际问题中有着非常经典的应用。例如，在一个序列中，如果除了某个元素出现奇数次之外，其余元素都出现偶数次，那么对整个序列进行一次异或运算后，所有出现偶数次的元素都会两两抵消，最终只会保留下那个出现奇数次的元素。因此可以在 $O(n)$ 的时间内直接求出答案。这类问题本质上就是利用了 “整体异或 = 各部分异或之和” 的可分解结构，将复杂的统计过程转化为一次简单的整体运算。

具体讲解可以看一下左神的这个视频

不仅如此，异或在某些特定结构下还会表现出明显的 周期性 。例如定义前缀异或：

可以得到如下规律：

也就是说，前缀异或的结果仅与 $n \bmod 4$ 有关，呈现出周期为 $4$ 的循环结构。对于任意区间 $[l, r]$ ，都有：

从而可以在 $O(1)$ 的时间内完成区间异或的计算。

这种周期性的本质来源于异或是 按位的模 2 加法：每一位只关心出现次数的奇偶性，而在连续整数中，各二进制位的变化具有固定的循环规律，叠加之后就形成了整体的周期性表现。正因为如此，许多看似需要枚举的大规模异或问题，都可以通过发现周期规律或转化为前缀异或来快速求解。

字符串异或变换#

题目链接

题目要点解析#