[ASDFZ]异或

给定一长度为 \(n\) 的序列 \(a_i\),\(q\) 次询问 \(a[l,r]\) 中选若干个数(可以不选)与 \(d\) 异或的最大值。

线性基的基础用法,区间直接用线段树维护线性基,时间复杂度 \(O(nlog^3n)\)。

但是这题 \(n\le 10^6\)。

考虑如果一个端点 \(r\) 固定,而 \(l\) 变化,那么只需要从 \(r\) 往左依次插入线性基,顺带记录线性基每一位插入的时间就可以解决。

如果右端点也变化,可以发现并不一定需要暴力重构线性基。

假设现在已经维护好了一个 \([1,r-1]\) 的从右往左依次插入的线性基,需要插入 \(r\),而且要在当前线性基所有元素之前插入。

实际上 \([1,r-1]\) 的线性基和 \([1,r]\) 区别仅仅是有若干位上移填补 \(r\) 的位置,模拟一下很好理解。

那么插入 \(a_r\) 时只需要把这几位依次下移即可。

时间复杂度:\(nlog(\max(a_i))\)

实现上线性基可以记录在原数组的编号,修改直接在原数组操作。

此题输入输出量极大,普通的快读读入时就会TLE。因此出题人提供了一个fread,fwrite模板。


在《[ASDFZ]异或》上留下第一个评论