感觉不是很难的一题，想了0.5h左右（思路歪了，不过想了一个大常数的两只\(\log\)做法233）
然后码+调了1h，除了一个SB的数组开小外基本上也没什么坑点
先讲一个先想到的方法，我们对于这种问题显然可以二分第\(k\)大，然后验证有多少个值小于等于它
然后考虑怎么判断，我们建一棵0/1Trie，然后枚举一个右端点，每次把整个Trie异或上这个点的权值
具体实现的话就是不断向下走的过程，当这一位为\(1\)时交换左右子树即可
然后相当于查小于等于一个数的数个数以及和，直接Trie上节点维护一下即可
这样是\(n \log \max{a_i}\log n\)的，由于\(a_i\)值域比较大而且直接跑满了，因此可能无法通过此题
然后慢慢就想到一种诡异的做法，先记录一下前缀异或和，然后考虑算出每个点为右端点时的最大值和左端点
这样有一个好处，我们每次用堆维护这\(n\)的点为右端点是答案的最大值，那么直接算出前\(k\)大即可
那么考虑如何计算，首先如果不考虑删除的话是挺简单的，我们建一棵可持久化0/1Trie，然后每个点在对应的Trie上找一个数和它异或值最大即可（类似于普通0/1Trie）
那么问题来了，我们统计完一个点的值时怎么删除能，可持久化数据结构一旦删除不是就全乱了么
其实不一定，由于这里只删一条已添加过的链，因此有一种奇妙的方法
我们记录左端点后找到右端点此时的Trie根节点编号，然后新开一个可持久化0/1Trie，然后直接在此时的版本上删去左端点对应的链即可
由于堆只需要取\(k\)次值，因此最多多产生\(k\)个版本，所以这部分的复杂度为\((n+k)\log \max{a_i}\)
然后加上堆的\(k\log n\)之后还是轻松通过此题，不过注意版本的数组大小要开大
CODE
#include<cstdio>
#include<cctype>
#include<queue>
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
typedef unsigned int u32;
const int N=5e5+5,R=32;
struct data
{
u32 val; int id;
inline data(const u32& Val=0,CI Id=0)
{
val=Val; id=Id;
}
friend inline bool operator < (const data& A,const data& B)
{
return A.val<B.val;
}
}; priority_queue <data> hp; long long ans;
int n,k,rt[N<<1],pos[N],cur; u32 a[N],pfx[N],ret;
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
char Fin[S],*A,*B;
public:
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
#undef tc
}F;
class Segment_Tree
{
private:
struct segment
{
int ch[2],size;
}node[N*(R+1)<<1]; int tot;
public:
#define lc(x) node[x].ch[0]
#define rc(x) node[x].ch[1]
#define S(x) node[x].size
inline void build(int& now,CI dep=R-1)
{
now=++tot; S(now)=1; if (!~dep) return; build(lc(now),dep-1);
}
inline void insert(CI lst,int& now,const u32& num,CI mv,CI dep=R-1)
{
now=++tot; node[now]=node[lst]; S(now)+=mv; if (!~dep) return;
if ((num>>dep)&1u) insert(rc(lst),rc(now),num,mv,dep-1);
else insert(lc(lst),lc(now),num,mv,dep-1);
}
inline void query(CI now,const u32& num,CI dep=R-1)
{
if (!~dep) return; if (S(node[now].ch[((num>>dep)&1)^1]))
ret|=1u<<dep,query(node[now].ch[((num>>dep)&1)^1],num,dep-1);
else query(node[now].ch[(num>>dep)&1],num,dep-1);
}
#undef lc
#undef rc
#undef S
}SEG;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (F.read(n),F.read(k),i=1;i<=n;++i) F.read(a[i]);
for (SEG.build(rt[0]),i=1;i<=n;++i)
{
pfx[i]=pfx[i-1]^a[i]; SEG.insert(rt[i-1],rt[i],pfx[i],1);
ret=0; SEG.query(rt[pos[i]=i],pfx[i]); hp.push(data(ret,i));
}
for (cur=n;k;--k)
{
data nw=hp.top(); hp.pop(); ans+=nw.val;
SEG.insert(rt[pos[nw.id]],rt[++cur],nw.val^pfx[nw.id],-1);
ret=0; SEG.query(rt[pos[nw.id]=cur],pfx[nw.id]); hp.push(data(ret,nw.id));
}
return printf("%lld",ans),0;
}