算法思路 Trie树 + 前缀和 + 贪心
此题是ACwing 143. 最大异或对的一个延伸,其实本质上就是再套了一层前缀和。因此此题可以从以下几个步骤来解决:
- 求前缀异或和
- 从左到右枚举所有前缀和,将每个前缀和分别插入Trie树并查询跟它异或值最大的配对,记录最大的异或值
为什么求前缀和可以work?
假设我们求的是普通加法和,不是异或和,那求完前缀和数组后可以在$O(1)$的时间内求一段区间$(i,j)$的和: $sum = prefix[j] - prefix[i - 1]$。
现在把 $+$ 换成 $\oplus$, 由于异或运算的逆运算还是异或本身,也就是$a \oplus b = c \rightarrow c \oplus b = a$, 那么区间$(i,j)$的和: $sum = prefix[j] \oplus prefix[i - 1]$。
为什么要引入Trie树?
朴素做法是直接遍历区间的左右端点,时间复杂度为$O(n^2)$。妥妥的TLE。
Trie树优化的是枚举左端点的这一步,假设用变量$i$来枚举右端点,朴素做法是让$j$从1枚举到i-1。Trie树可以实现在$log(21)$的时间下找到最优的左端点。因此整个算法的时间复杂度优化到$O(nlog 21)$级别。
贪心性质
注意到题目要求输出长度最小的区间,并且右端点也应该最小。这2点在代码中如何保证呢?
-
首先区间长度最小。我们每次向Trie树中插入一个数后,应当把它在原数组中的坐标也保存下来,而且如果该数重复出现,应当覆盖掉原来的坐标。比如求出前缀和数组为: [0,1,1,2],当向Trie树插入第二个1时,对应的1的坐标应该更新为3(假设下标从1开始)。这样做保证了每次查询返回的最大异或配对的坐标都是离当前遍历坐标最近的,因此保证了最小区间。可以用反证法证明这么做一定保证了能取到长度最小的区间(这里就不给出了)。
-
接着是右端点最小。这个很简单,由于我们是从左向右遍历,只需要让异或值严格大于当前最大值时再更新最大值就可以保证了。
做题时可能会遇到的坑(反正小白我是都踩了…)
- trie数组的大小不是N,而是N * 21(因为一个数需要占21个存储单元)
- 异或运算的优先级小于比较运算符!(所以不能写成 t ^ a[i] > max,要加括号!)
- 边界问题。这取决于先插入还是先查询。我这里采用先插入再查询的方式,最后要特判只有1个数和全部的数都相同的情况。(2021.2.3 更新:其实还是先查询后插入比较方便,只需在开始时插入0即可,不需要特判,代码已贴出)
C++ 代码 + 注释 (基本按照y总算法基础课上的模板来写)
#include<iostream>
using namespace std;
const int N = 100010;
int a[N], trie[N * 21][2], pos[N * 21], idx, l, r;
int mm = -1;
void insert(int id)
{
int p = 0, x = a[id];
for(int i = 20; i >= 0; i--){
int u = x >> i & 1;
if(!trie[p][u]) trie[p][u] = ++idx;
p = trie[p][u];
}
pos[p] = id; // 记录一下插入的数的下标
}
pair<int, int> query(int id) // 这里需要返回2个值,一个是最大的异或配对,一个是这个配对的下标
{
int p = 0, res = 0, x = a[id];
for(int i = 20; i >= 0; i--){
int u = x >> i & 1;
if(trie[p][!u]){
p = trie[p][!u];
res = res * 2 + !u;
}else{
p = trie[p][u];
res = res * 2 + u;
}
}
return {res, pos[p]};
}
int main()
{
int n;
pair<int, int> t;
cin>>n;
for(int i = 1; i <= n; i++) {
cin>>a[i];
a[i] ^= a[i - 1];
insert(i);
t = query(i);
if((t.first ^ a[i]) > mm){ // 如果异或值严格大于当前最大值,更新一下最大值,还有区间端点
mm = (t.first ^ a[i]);
l = t.second + 1;
r = i;
}
}
if(n == 1){ // 特判只有一个数的情况
mm = a[1];
l = r = 1;
}
if(l == 2 && r == 2) l = r = 1; // 特判全部的数都相同的情况
cout<<mm<<' '<<l<<' '<<r<<endl;
return 0;
}
先查询后插入的实现(无需特判)
int main()
{
int n;
pair<int, int> t;
cin>>n;
insert(0); // 预先插入一个0
for(int i = 1; i <= n; i++) {
cin>>a[i];
a[i] ^= a[i - 1];
t = query(i);
if((t.first ^ a[i]) > mm){ // 如果异或值严格大于当前最大值,更新一下最大值,还有区间端点
mm = (t.first ^ a[i]);
l = t.second + 1;
r = i;
}
insert(i);
}
cout<<mm<<' '<<l<<' '<<r<<endl;
return 0;
}
数据已经更新,不先insert(0)的话,会wa一个样例,上面下面两份一样;
错误原因:
a[i]一直^a[i - 1],有可能答案是 i — j 一路异或过去,没有insert(0)的话,会偏小,正整数异或0都会为其本身,
### 没有insert(0)的话,输出的是
会少了数本身操作的情况
加括号!!!
请教一下,插入和查询的顺序,会影响到什么,以至于答案不一样,谢谢了!
本质上是一样的,因为当Trie树中插入的点数大于等于2时,对于一个插入的数,不可能查询到自己。但如果树中点数为1会有一些问题。比如只有一个数的时候,先插入再查询返回的区间的是$(2, 1)$`(因为第一个数下标是1,$l$被更新为2),但我们想要的是$(1, 1)$。同理,全部的数相同时,会返回$(2, 2)$,而正确答案是$(1, 1)$。所以我最后需要另外加2个特判来处理这些边界情况。不过很感谢你的问题,我后来想了一下这么写比较啰嗦、不够优雅,其实先查询再插入代码可以很简洁!只需要一开始插入0就好了,无需特判。原文已更新代码~
谢谢!
想请教一下 为什么异或和就是所有数异或呢?这是定义吗?
是的,异或可以看成不进位的加法
好的,谢谢!!!
为啥trie树插入点数大于2时对于一个插入的数不可能查询到自己?
请教一下,l = t.second + 1 此处为啥需要+1呢
$[l,r]$这一段区间和用前缀和$a[r] - a[l - 1]$来计算,query求出的是前面这个$l - 1$,因此答案的$l$需要加一