可持久化trie
考虑像主席树建树,然后可以处理trie的进阶问题
最大异或和
题目描述
给定一个非负整数序列 \(\{a\}\),初始长度为 \(N\)。
有 \(M\) 个操作,有以下两种操作类型:
A x
:添加操作,表示在序列末尾添加一个数 \(x\),序列的长度 \(N\) 加 \(1\)。Q l r x
:询问操作,你需要找到一个位置 \(p\),满足 \(l \le p \le r\),使得:\(a[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x\) 最大,输出最大值。
solution
可持久化trie上维护前缀xor,然后就考虑在\(l-1\sim r-1\)的s找到xor\(s_n\oplus x\)的最大异或,然后可持久化trie上维护的r-1版本可以处理1~r-1,但是trie好像不支持可减性,然后就是每个节点记录以当前节点为根的子树中,最后的版本是lst,然后就是子树中lst<l-1就不考虑,否则就正常做
[TJOI2018] 异或
题目描述
现在有一颗以 \(1\) 为根节点的由 \(n\) 个节点组成的树,节点从 \(1\) 至 \(n\) 编号。树上每个节点上都有一个权值 \(v_i\)。现在有 \(q\) 次操作,操作如下:
- \(1~x~z\):查询节点 \(x\) 的子树中的节点权值与 \(z\) 异或结果的最大值。
- \(2~x~y~z\):查询节点 \(x\) 到节点 \(y\) 的简单路径上的节点的权值与 \(z\) 异或结果最大值。
solution
首先只有询问,考虑直接分开处理
对于询问1,一个子树内的dfn序连续,就是把树的dfn序搞出来就是上面那题
对于询问2,就考虑分成两条链,然后考虑按照树的父子关系建可持久化trie,也是类似
[THUSC2015] 异或运算
题目描述
给定长度为 \(n\) 的数列 \(X={x_1,x_2,...,x_n}\) 和长度为 \(m\) 的数列 \(Y={y_1,y_2,...,y_m}\),令矩阵 \(A\) 中第 \(i\) 行第 \(j\) 列的值 \(A_{i,j}=x_i\ \operatorname{xor}\ y_j\),每次询问给定矩形区域 \(i∈[u,d],j∈[l,r]\),找出第 \(k\) 大的 \(A_{i,j}\)。(\(n\le1000,m\le300000,p\le500\))
solution
根据数据范围不难猜到需要\(O(pn\log w)\)的复杂度
所以考虑对于一个数x,和一个数列Y如何算第k大,先将数列建成trie,维护左右儿子各有多少数,然后像权值线段树一样处理第k大。若有多个x则每次处理多个(有点像树状数组套线段树)。考虑如何拓展Y
很容易想到把Y持久化,然后考虑左右儿子各有多少数,满足可减性,即可直接处理(并且上面的题也可以使用)
标签:持久,trie,异或,权值,oplus,节点 From: https://www.cnblogs.com/zhy114514/p/18028186