给定一个长度为$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