原理

坑。

例题

P哥的桶

首先有一道很水的例题

题意

一共有 n 个数组,可以向某一个数组里增加一个数,或者询问区间内所有数组里数组可能的最大异或和。

思路

线性基套上一个线段树,可以学习一下基本插入和查询操作。

最大XOR和路径

题意

在可能有重边自环的有向图里寻找一条从 1 到 $N$ 的路径,可以重复经过某些点或边,最大化经过的点权 XOR和。

思路

首先我们考虑任意一条从 1 到 $N$ 的简单路径。

由于可以重复经过一些点,也就是我们可以向外走一个环再回来。

发现从链上一点到环之间的路径经过两次对答案没有贡献,所以我们可以预处理出所有环的答案丢到线性基里贪心选取。

这种做法对一开始选取的简单路径没有要求,因为假设存在更优的路径,它和当前的这条路径形成的环也被加进了线性基里,如果选取了这个环,就相当于走了另外一条更优的路径。

代码

致谢

我的板子是从 Menci 那里学来的,感谢学长 qwq。