BZOJ 3261 最大异或和

发布于 2017-06-29  179 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3261

题意:对于一个初始长度为 n 的序列 a,维护 m 个操作,为下两种之一:

A x :添加操作:表示在序列末尾添加一个数 x

Q l r x:询问操作:找到一个位置 p,满足 \(l\leq p\leq r\) 且使得:\(a_p\oplus a_{p+1}...\oplus a_{n}\oplus x\) 最大,输出最大值。  


约定

二元组 (l,r) 表示从\(a_l\) 到\(a_r\) 的连续异或值


为了做 3261 得先会做 3689 ...

现在我们考虑这道题,在数列后面加数还要查询区间最大后缀异或值,是不好搞的... 所以有一个重要的思想是转换成前缀查询:

我们知道异或是满足结合律的,且 a^a=0,那么 (l,r)=(1,l-1)^(1,r),大概就是把 (1,r) 的前一部分提出来即可

所以我们可以只维护前缀异或值,记为 sum,每次查询实际上为找到一个满足条件的 p 使得 x^sumn^sump 最大

如果没有区间限制,询问是在整个序列上的,建立 trie 树贪心即可,同 3689,但是有区间限制,所以每次我们需要单独考虑区间中的数

可持久化即可。每次在 tire 树上贪心,每棵树维护 size,通过 l-1 和 r 两棵树区间减查询即可

 


一个非常弱的准退役OIER