题解 P4735 【最大异或和】

2018-12-20 10:59:45


异或满足可减性,所以可以维护前缀和,然后

$$\mathrm{a[p]\ xor\ a[p+1]\ xor\ ...\ xor\ a[n]\ xor\ x=s[p-1]\ xor\ s[n]\ xor\ x}$$

然后就只要维护 $s[]$ 。添加很好维护,重点是如何查询。

此时查询转变为:已知 $val=\mathrm{s[n]\ xor\ x}$ ,求一个 $p\in[l-1,r-1]$ ,使得 $\mathrm{s[p]\ xor\ val}$ 最大。

可以构建一颗可持久化 $\mathrm{Trie}$ ,第 $i$ 个版本为插入了 $s[i]$ 后的 $\mathrm{Trie}$ 树。

每次查询,从根节点开始,贪心地选与这一位相反的值。

此外,还有一个 $l-1\leq p\leq r-1$ 的限制。

先考虑 $p\leq r-1$ ,查询第 $r-1$ 个版本的 $\mathrm{Trie}$ 即可,因为此时不可能访问到 $r-1$ 之后的 $s$ 。 再考虑 $l-1\leq p$ ,对每个节点维护一个 $latest$ 值,表示子树中所有 $s$ 值的下标的最大值。这样,在查询时只访问 $latest\geq l-1$ 的节点就行了。

然而Luogu上要吸氧,BZOJ上完全能过。

代码见blog