BZOJ 3261 最大异或和


题目链接: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 两棵树区间减查询即可

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3261 最大异或和


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,