字符串

利用可持久化01Trie解决区间异或一类问题

 2020.06.16 22:16  2023.09.01 18:14  ACM  Trie  可持久化  可持久化01Trie  字符串 󰈭 3545字

为了补校赛网络的I题，就去看了异或粽子，然后就看到了Trie以及可持久化01Trie，进而就有了这篇博客qaq 借助这几道题学习一番可持久化01Trie的有关知识参考博客：可持久化01Trie + 异或粽子（精心) P4735 最大异或和题目要求区间中某个位置p∈[L, R]使得a[p] ^ a[p + 1]^ ... ^ a[n] ^ x最大，其中p, L, R给定，允许在该序列末尾动态添加数字。首先根据异或的性质等价转化要求的表达式：``a[p] ^ a[p + 1]^ … ^ a[n] ^ x = x ^ sum ^ a[1] ^ a[2] ^ … ^ a[p - 1] `，其中sum是整个序列的异或值；因而在某个给定的状态下，我们只需要找位置p-1使得其前缀异或值和x^sum异或值最大即可。为了完成动态修改、查询的工作，我们使用可持久化01Trie，其思想与主席树类似（尽管我还没学但是不妨碍我学会01Trie)。 ...