给定一个长度为$n$的数组$a$,取$k$个各不相同的连续区间$[l,r]$ 使得这些区间所有元素的异或和的和最大,求这个最大值
($ 1 \le n \le 5 \times 10^5,1\le k \le min(\frac{n(n-1)}{2},2\times 10^5),0\le a_i \le 4294967295$)感谢@oy的贡献
分析题意,即找出$n$个数中互不相同且异或和最大的前$k$段区间。
用异或前缀和$s[i]$表示$a[1]\oplus a[2]\oplus … \oplus a[i]$。根据异或运算的性质,区间$[l,r]$的异或和即为$s[r] \oplus s[l-1]$。
将$s[1]$到$s[n]$依次插入$01trie$树中,每次找出对于固定的右端点$r$,与$s[r]$异或值最大的$s[l]$。显然,此次操作找到的是固定右端点为$r$时的最大区间异或和。
将每个不同的$r$值所对应的最大区间异或和插入堆中,显然堆顶的元素即为$n$个数中任意区间的最大异或和。取出堆顶元素,并同时得到这是以$r$为右端点的第$1$大区间异或和。向堆中插入以$r$为右端点的第$2$大区间异或和。
在查询以$r$为右端点的第$k$大区间异或和时,只需稍微更改在$01trie$树上查找的方式即可,与主席树查询区间第$k$小数的思想类似。由于需要访问$01trie$树的历史状态,因此$01trie$需要可持久化。
注意:以$r$为右端点的区间异或和一共只有$r$个,因此查询以$r$为右端点的第$r+1$大区间异或和是没有意义的。
另外,在将(1<<d)
这样的式子转long long
时,不能写成(long long)(1<<d)
,而是((long long)1<<d)
。
代码如下:
1 | #include<bits/stdc++.h> |
$p.s.$洛谷评测机有点小慢,不开O2
会小概率发生TLE QwQ