前言(吐槽)

其实我是一直知道这玩意,但一直没学过。最近重新在看字符串算法,其中有一节讲到字典树可以处理位异或运算

知道原理但没手写过,结果隔天的练习赛就遇到了一题。。。(该来的还是会来的)

开始吐槽(其实是学习和抄板子)


板子

01-trie 是指字符集为 ${0,1}$ 的 字典树。常用来维护数组的异或极值和异或和。

01-trie 支持修改(删除 + 重新插入),和全局加一(即:让其所维护所有数值递增 1,本质上是一种特殊的修改操作)。

这里先上个简单的板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int tol; //节点个数 
LL val[32*MAXN]; //点的值
int ch[32*MAXN][2]; //边的值

void init(){ //初始化
tol=1;
ch[0][0]=ch[0][1]=0;
}

void insert(LL x){ //往 01字典树中插入 x
int u=0;
for(int i=32;i>=0;i--){
int v=(x>>i)&1;
if(!ch[u][v]){
//如果节点未被访问过
ch[tol][0]=ch[tol][1]=0; //将当前节点的边值初始化
val[tol]=0; //节点值为0,表示到此不是一个数
ch[u][v]=tol++; //边指向的节点编号
}
u=ch[u][v]; //下一节点
}
val[u]=x; //节点值为 x,即到此是一个数
}

LL query(LL x){ //查询所有数中和 x异或结果最大的数
int u=0;
for(int i=32;i>=0;i--){
int v=(x>>i)&1;
//利用贪心策略,优先寻找和当前位不同的数
if(ch[u][v^1]) u=ch[u][v^1];
else u=ch[u][v];
}
return val[u]; //返回结果
}

观察建立树的过程,其实就和字典树差不多,上面的板子是在叶子处存值,但实际也会有各种存法(比如每个点都存),例如下面这题

(吐槽:太久没用数组建过树了,忘记怎么建了)


题(暴毙)

2021“MINIEYE杯”中国大学生算法设计超级联赛(1)-6:XOR sum

题意

给一个整数数组,你需要找到最短的区间,其按位异或和不小于. 如果有多个,找出左端点最左的

题解

异或运算里,任意x的逆元是本身,故对于前缀和pre[i]pre[j],ij的异或和可以表示为pre[i]^pre[j]

这亚子我们去求一个子串的异或和就简单灰常多啦

我们考虑字典树去维护前缀异或和,由于是要求左右端点,所以我们每往字典树中新增一个值,则查找前面的有没有适合的

那这时我们先考虑一个问题。显然一个前缀异或和可能对应好多个前缀子串,那这棵树该存些什么?

因为是边存边处理,然后要尽可能短的子串,所以在相同前缀异或和的情况下,我们存最右边的那个的下标

好了,那如何保证pre[i]^pre[j]>=k?

显然当k的某位为1时,树只能往相异的方向走;为0时则要考虑相异方向的值和同向子树的最大。那我们在每个节点都存最右的值,即可在读到0的时候停下读标号即可

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int p[4000010][2]={0},val[4000010]={0},a[100010]={0};
//记录树的左右分叉(节点下标),树的节点值(最右下标 ),前缀异或和
int main(){
int t;
scanf("%d", &t);
while(t--){
int n,k;
scanf("%d %d", &n,&k);
for(int i=1;i<=n;i++){
scanf("%d", &a[i]);
a[i] ^= a[i-1];
}
int l=-1,r=n,num=1;//记录答案左端点、右端点、数的节点数
val[1]=-1;
p[1][0] = p[1][1] = 0;//初始化树根
for(int i=0;i<=n;i++){//从0开始: a[i] = a[i]^0
int nowl=-1;//记录以i为右当前查到的合适左位置
int x=1;//记录走到的节点标号
for(int j=29;j>=0;j--){
int abit = (a[i]>>j)&1; //记录a[i]第j位;
if((k>>j)&1)//如果k的第j位是1,那只能走abit的相反方向
x = p[x][abit^1];
else{ //如果k的第j位为0则要考虑abit的相反方向和同方向下一层的最大
if(p[x][abit^1])
nowl = max(nowl, val[p[x][abit^1]]);
x = p[x][abit];
}
if(!x)break;//如果找不到路,则弹出
}
if(x)
nowl = max(nowl, val[x]);//如果成功走到最底层也要做一次取最大

//更新l,r
if(nowl > -1 && i-nowl < r-l)
l = nowl, r = i;

//将a[i]加入字典树中
x=1;
for(int j=29;j>=0;j--){
int abit = (a[i]>>j)&1;
if(!p[x][abit]){//如果不存在节点就新建
p[x][abit] = ++num;
p[num][0] = p[num][1] = 0;
}
x = p[x][abit];
val[x] = i;//这里不用比较,i肯定比前面的大,直接覆盖就行;
}
}
if(l>-1)printf("%d %d\n", l+1,r);
else printf("-1\n");
}
return 0;
}

杭电多校2的第4题貌似也是字典树,但我还没搞懂怎么弄,先鸽着。。。

2021“MINIEYE杯”中国大学生算法设计超级联赛(2)-4:I love counting