4s
512MB
伏特再次找到了工程师，请他们设计铁轨。工程师很快给出了一张模板图纸作为候选方案。
图纸上 $n$ 段铁轨排成一行，依次编号为 $1, \dots, n$。根据工程师们的设计，第 $i$ 段铁轨的尾部只能和第 $i+1$ 段铁轨的头部相连 $(1\leq i < n)$，否则铁轨会变的极为不稳定。
伏特不必铺设所有的铁轨。伏特可以选择一个编号区间，如 $[l, r]$，然后下令只铺设编号在区间 $[l, r]$ 中的铁轨。显然区间的选择方案一共只有 $\frac{n(n+1)}{2}$ 种。
跳蚤国拥有独特的材料科学，每段铁轨都可以使用两种材料中的一种构建，稳定度分别为 $a_i,b_i$，且不同段铁轨可以使用不同材料。根据工程师们的建模，对于一个区间选择方案 $[l, r]$，如果第 $i$ 段铁轨选择了稳定度为 $p_i$ 的材料 ($p_i \in \{a_i, b_i\}$)，那么铺设区间 $[l, r]$ 中的所有铁轨的总稳定度为该区间内所有 $p_i$ 的异或和，即 $p_l \oplus p_{l+1} \oplus \cdots \oplus p_r$，其中 $\oplus$ 表示异或。
对于每个区间 $[l, r]$，工程师早已算好了在所有可能的材料选择方案中总稳定度的最大值，称之为该区间的最优稳定度。
现在伏特找到了你，希望你能帮工程师们验算一番。请你求出所有可能的区间中，第 $k$ 小的最优稳定度是多少。
\(n\le 10^5,m\le 30\)
先来一些基本转化。
设 \(c_i=a_i\oplus b_i\)，那么求一个区间的最有稳定度也就是求区间的 \(a\) 的异或和在这个区间的 \(c\) 的线性基能异或出的最大值。
看一下部分分，随机数据的做法也是容易的。枚举左端点 \(l\)，那么期望右端点在 \(l+2log n\) 左右时，线性基会满，那么后面答案一定是 \(2^m-1\)。
\(a_i=b_i\) 的数据是容易的 trie 树二分，\(a_i=0\) 的情况又复杂了。
现在要求两两之间线性基异或的最大值的第 \(k\) 大。先考虑如何求出两两之间的线性基。在随机数据的提示下，我们知道了线性基是有势能的。考虑扫描线右端点，此时互不相同的线性基最多有 \(m\) 个。可以记录 \(b_{i,j}\) 表示以 \(i\) 为右端点的，大小为 \(j\) 的线性基是什么，在记录下一个 \(l_{i,j}\) 以及 \(r_{i,j}\) 表示对于 \(l_{i,j}\le k\le r_{i,j}\)，\([k,i]\) 的线性基为 \(b_{i,j}\)。
求答案是容易的。总共有 \(nlogn\) 个互不相同的线性基，那么线性基的最大值也是 \(nlogn\) 个。直接排序扫一下就行了。复杂度 \(nlog^2n\)。
然后我们开始往正解想。看题解得知有一个性质，设 \(f(T,x)\) 为 \(x\) 异或线性基 \(T\) 当中的数最大是多少，\(g(T,x)\) 表示 $x4 异或线性基 \(T\) 当中的数出来最少是多少。那么 \(f(T,x\oplus y)=f(T,x)\oplus g(T,y)\)
如果这样子的话，有些信息就支持合并了。求出 \(a\) 的前缀异或和 \(s\)，那么 \(f(s_r\oplus s_{l-1},x\oplus y)=f(T,s_{l-1})\oplus g(T,s_r)\)。对于每个点 \(r\)，记录 \(p_{r,i}\) 为 \(s_r\) 在 \(r\)为右端点大小为 \(i\) 的线性基里面异或出的最大值，\(q_{l,i}\) 为 \(s_{l-1}\) 在 \(l\) 为左端点的大小为 \(i\) 的线性基里面异或出的最大值。那么区间 \([l,r]\) 贡献就是能算的了。
考虑二分后对每种大小的线性基统一统计答案，那么一个 \(p_{x,i}\) 可以和 \(l_{x,i}\le y\le r_{x,i}\) 的 所有 \(q_{x,i}\) 异或。建 \(m\) 个可持久化 trie 树，并在所有 trie 上面进行二分，复杂度 \(O(nlog^2n)\)，但空间也达到了常数很大的 \(O(nlog^2n)\)
巧妙地，我们并不用把整棵可持久化 trie 树全部建出来，我们可以只建出这一层的信息，然后在这一层记录下正常建可持久化 trie 在递归中记录的信息。二分时也是记录下信息，然后跑就行了。空间复杂度 \(O(nlogn)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,B=32;
int n,a[N],b[N],r[N][B],g[N][B],h[N][B],ans,tr[B][N][2],f[B][N],sz[B][N],d[B][N],l[B][N];
long long s,k;
struct basis{
int a[B];
int insert(int x)
{
for(int i=29;~i;--i)
{
if(x>>i&1)
{
if(!a[i])
return a[i]=x,1;
x^=a[i];
}
}
return 0;
}
int askmx(int x)
{
for(int i=29;~i;--i)
if(!(x>>i&1))
x^=a[i];
return x;
}
int askmn(int x)
{
for(int i=29;~i;--i)
if(x>>i&1)
x^=a[i];
return x;
}
void operator=(const basis&p){
memcpy(a,p.a,sizeof(a));
}
void clr()
{
memset(a,0,sizeof(a));
}
}p[B];
int main()
{
memset(g,-1,sizeof(g));
memset(h,-1,sizeof(h));
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=1;i<=n;i++)
scanf("%d",b+i),b[i]^=a[i];
for(int i=2;i<=n;i++)
a[i]^=a[i-1];
for(int i=1;i<=n;i++)
{
memcpy(r[i],r[i-1],sizeof(r[i]));
r[i][0]=i;
p[0].clr();
if(!b[i])
g[i][0]=a[i-1];
for(int j=29;~j;j--)
{
if(r[i][j]==r[i][j+1])
continue;
if(p[j].insert(b[i]))
{
for(int k=r[i][j+1]+1;k<=r[i][j];k++)
g[k][j+1]=p[j].askmn(a[k-1]);
p[j+1]=p[j];
r[i][j+1]=r[i][j];
}
}
for(int j=0;j<=30;j++)
{
if(r[i][j]^r[i][j+1])
h[i][j]=p[j].askmx(a[i]);
}
}
for(int i=0;i<=30;i++)
for(int j=1;j<=n;j++)
f[i][j]=r[j][i],d[i][j]=r[j][i+1],l[i][j]=j-1;
for(int i=30;~i;i--)
{
memset(tr,s=0,sizeof(tr));
memset(sz,0,sizeof(sz));
for(int j=0;j<=30;j++)
{
for(int k=1;k<=n;k++)
{
if(g[k][j]==-1)
continue;
sz[j][k]=sz[j][tr[j][l[j][k]][g[k][j]>>i&1]]+1;
tr[j][k][g[k][j]>>i&1]=k;
tr[j][k][g[k][j]>>i&1^1]=tr[j][l[j][k]][g[k][j]>>i&1^1];
l[j][k]=tr[j][l[j][k]][g[k][j]>>i&1];
}
}
for(int j=0;j<31;j++)
{
for(int k=1;k<=n;k++)
{
if(~h[k][j])
{
s+=sz[j][tr[j][f[j][k]][h[k][j]>>i&1]]-sz[j][tr[j][d[j][k]][h[k][j]>>i&1]];
}
}
}
if(s<k)
{
k-=s,ans|=1<<i;
for(int j=0;j<31;j++)
for(int k=1;k<=n;k++)
if(~h[k][j])
f[j][k]=tr[j][f[j][k]][h[k][j]>>i&1^1],d[j][k]=tr[j][d[j][k]][h[k][j]>>i&1^1];
}
else
{
for(int j=0;j<31;j++)
for(int k=1;k<=n;k++)
if(~h[k][j])
f[j][k]=tr[j][f[j][k]][h[k][j]>>i&1],d[j][k]=tr[j][d[j][k]][h[k][j]>>i&1];
}
}
printf("%d",ans);
}