- 给定 $n$ 和序列 $a_1,a_2,\cdots,a_n$，$b_1,b_2,\cdots b_n$。
- 定义一个区间 $[l,r]$ 的权值为：对于所有满足 $p_i\in {a_i,b_i}$，$\oplus_{i=l}^r p_i$ 的序列 $p_1,p_2,\cdots p_n$ 的最大值。
- 求左右端点满足 $1\leq l\leq r\leq n$ 的区间中，第 $k$ 小的权值是多少（可重）。
- $1\leq n\leq 10^5,0\leq a_i,b_i\lt 2^{30},1\leq k\leq \frac{n(n+1)}2$。
sol
初步思考
- 这种题目比较容易想到线性基。
- 但是线性基是其中每个数都可以选或不选，而这题是类似于连续区间二选一。
- 线性基就不能做了吗？当然不是，假设刚开始全部选 $a$，那么选择一些位置把它变成 $b$ 这种类型就是线性基能做的了。
问题转化
- 记 $c_i=a_i\oplus b_i,s_i=\oplus_{j=1}^i a_j$，区间 $[l,r]$ 的权值转化为：$s_r\oplus s_{l-1}$ 再异或上若干个 $c_i$ 的最大值。
- 线性基求和 $x$ 异或的最大值的方法为：从高到低枚举每一位，若这一位 $x$ 为 $0$，则异或上线性基上这一位的数。
- 设 $f(x,T)=\max_{y\in T}(x\oplus y)$，其中 $x$ 是一个数，$T$ 是一个线性基。
- 暴力做法：固定左端点 $l$，移动右端点 $r$ 时维护线性基 $T$，求出每个区间的权值 $f(s_r\oplus s_{l-1},T)$，最后求第 $k$ 小值。
继续思考
- 考虑优化暴力做法。固定左端点，由于线性基维数不超过 $m$，故不同的右端点本质不同的线性基至多有 $m+1$ 种（即维数分别为 $0,1,\cdots m$）。移动右端点时，线性基维数可能增加 $1$，也有可能不增加。
-
考虑改为：对于右端点 $r$，维护所有左端点为 $1,2,\cdots,r$ 的线性基。右端点从 $r-1$ 移动到 $r$ 时，一定是一个后缀 $p,p+1,\cdots,r$ 的线性基维数 $+1$，可以直接暴力更新，复杂度 $O(nm^2)$。
-
现在求的 $f(s_r\oplus s_{l-1},T_{l,r})$ 和 $l,r$ 都有关，虽然在移动右端点时维护出了不同的 $T$，但是带入无法解决。
- 设 $g(x,T)=\min_{y\in T}(x\oplus y)$，由于 $f$ 相当于 $x$ 某位为 $1$ 就异或那一位的线性基上的值，$g$ 相当于 $x$ 某位为 $0$ 就异或那一位的线性基上的值，那么 $f(s_r\oplus s_{l-1},T_{l,r})$ 等于 $f(s_r,T_{l,r})\oplus g(s_{l-1},T_{l,r})$。
- 现在 $T_{l,r}$ 可以增量维护，和右端点移动无关的 $f(s_r\oplus s_{l-1},T_{l,r})$ 就能维护了，而和右端点移动有关的 $g(s_r,T_{l,r})\oplus g(s_{l-1},T_{l,r})$ 由于本质不同的只有最多 $m$ 个，所以可以每次暴力重新求。
上述实现
- $lv[x][l]$ 表示基大小为 $x$，左端点为 $l$ 时代入 $s[l-1]$ 的最小值。
- $rv[x][r]$ 表示基大小为 $x$，右端点为 $r$ 时代入 $s[r]$ 的最大值。
-
$lp[x][r]/rp[x][r]$ 表示基大小为 $x$，右端点为 $r$ 时左端点合法区间的左右端点。
-
具体来说，$lv$ 可以通过暴力往左枚举左端点，加入当前数扩大线性基，直到发现当前左端点当前数不能扩大线性基就停止。$rv/lp/rp$ 可以维护满足 $i..r$ 基大小为 $x$ 的最大的 $r$，在这些位置加入当前数扩大线性基合并。
求解答案
- 二进制从高到低确定每一位，假设当前确定到从高到低第 $w$ 位。
- 枚举基大小，对于不同的右端点，求出合法左端点区间中，$g$ 和当前右端点 $f$ 值前 $w$ 位相同的数的数量，具体实现使用
two-pointers。 - 求和后和 $k$ 比较，如果 $<k$，说明答案这位为 $1$，将 $k$ 减去当前数量，并将所有 $f$ 的这一位异或（即之后要找这一位不同的）。
//40pts
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int m=30;
int n,a[110000],b[110000],c[110000],s[110000]; ll k;
int lv[32][110000],rv[32][110000],lp[32][110000],rp[32][110000],v[32][110000];
unordered_map<int,int> mp;
struct Basis{
int tot,v[32];
Basis(){ tot=0; memset(v,0,sizeof(v));}
bool ins(int x){
for (int i=m-1;i>=0;i--)
if ((x>>i)&1) x^=v[i];
for (int i=m-1;i>=0;i--)
if ((x>>i)&1){
v[i]=x; tot++;
for (int j=m-1;j>i;j--)
if ((v[j]>>i)&1) v[j]^=x;
return true;
}
return false;
}
int querymax(int x){
for (int i=m-1;i>=0;i--)
if (!((x>>i)&1)) x^=v[i];
return x;
}
int querymin(int x){
for (int i=m-1;i>=0;i--)
if ((x>>i)&1) x^=v[i];
return x;
}
} A[110000],B[110000];
vector<int> p,q;
void upd(int i){
A[i].ins(c[i]); for (int x:p) A[x].ins(c[i]);
q=p; p.clear(); p.push_back(i);
for (int x:q)
if (A[x].tot>A[p.back()].tot) p.push_back(x);
}
int main(){
scanf("%d%lld",&n,&k);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
s[i]=s[i-1]^a[i];
}
for (int i=1;i<=n;i++){
scanf("%d",&b[i]);
c[i]=a[i]^b[i];
}
for (int i=1;i<=n;i++){
for (int j=i;j>=1&&(B[j].ins(c[i])||i==j);j--)
lv[B[j].tot][j]=B[j].querymin(s[j-1]);
upd(i);
for (int j=0;j<(int)p.size();j++){
rv[A[p[j]].tot][i]=A[p[j]].querymax(s[i]);
lp[A[p[j]].tot][i]=(j+1<(int)p.size()?p[j+1]+1:1); rp[A[p[j]].tot][i]=p[j];
}
}
int ans=0;
for (int i=m-1;i>=0;i--){
for (int j=0;j<=m;j++)
for (int k=1;k<=n;k++)
v[j][k]=((v[j][k]<<1)|(rv[j][k]>>i&1));
ll tot=0;
for (int j=0;j<=m;j++){
mp.clear(); int l=1,r=0;
for (int k=1;k<=n;k++){
if (!lp[j][k]) continue;
while (l<lp[j][k]) mp[lv[j][l++]>>i]--;
while (r<rp[j][k]) mp[lv[j][++r]>>i]++;
tot+=mp[v[j][k]];
}
}
int c=(tot<k); if (c) k-=tot;
for (int j=0;j<=m;j++)
for (int k=1;k<=n;k++)
v[j][k]^=c;
ans=(ans<<1|c);
}
printf("%d\n",ans);
return 0;
}
- 发现 TLE 了，因为直接这样子做常数非常大，因为求相同的数的数量时，$f/g$ 值可能很大，需要使用 $map/unordered_map$ 或 手写哈希表 等数据结构。
- 怎么办呢，可以发现，这一位做完后，前几位再也不会修改了，所以可以将前几位重标号，这样就可以通过此题，时间复杂度 $O(nm^2)$。
```cpp
//Accepted
include
using namespace std;
typedef long long ll;
const int m=30;
int n,c[110000],s[110000],mp[4100000],num[4100000],val[4100000]; ll k;
int lv[32][110000],rv[32][110000],lp[32][110000],rp[32][110000],u[32][110000],v[32][110000];
struct Basis{
int tot,v[32];
Basis(){ tot=0; memset(v,0,sizeof(v));}
bool ins(int x){
for (int i=m-1;i>=0;i--)
if ((x>>i)&1) x^=v[i];
for (int i=m-1;i>=0;i--)
if ((x>>i)&1){
v[i]=x; tot++;
for (int j=m-1;j>i;j--)
if ((v[j]>>i)&1) v[j]^=x;
return true;
}
return false;
}
int querymax(int x){
for (int i=m-1;i>=0;i--)
if (!((x>>i)&1)) x^=v[i];
return x;
}
int querymin(int x){
for (int i=m-1;i>=0;i--)
if ((x>>i)&1) x^=v[i];
return x;
}
} A[110000],B[110000];
vector
void upd(int i){
A[i].ins(c[i]); for (int x:p) A[x].ins(c[i]);
q=p; p.clear(); p.push_back(i);
for (int x:q)
if (A[x].tot>A[p.back()].tot) p.push_back(x);
}
int main(){
scanf("%d%lld",&n,&k);
for (int i=1;i<=n;i++) scanf("%d",&s[i]);
for (int i=1;i<=n;i++){
scanf("%d",&c[i]);
c[i]^=s[i]; s[i]^=s[i-1];
}
for (int i=1;i<=n;i++){
for (int j=i;j>=1&&(B[j].ins(c[i])||i==j);j--)
lv[B[j].tot][j]=B[j].querymin(s[j-1]);
upd(i);
for (int j=0;j<(int)p.size();j++){
rv[A[p[j]].tot][i]=A[p[j]].querymax(s[i]);
lp[A[p[j]].tot][i]=(j+1<(int)p.size()?p[j+1]+1:1); rp[A[p[j]].tot][i]=p[j];
}
}
int ans=0;
for (int i=m-1;i>=0;i--){
for (int j=0;j<=m;j++)
for (int k=1;k<=n;k++){
v[j][k]=((v[j][k]<<1)|(rv[j][k]>>i&1));
u[j][k]=((u[j][k]<<1)|(lv[j][k]>>i&1));
}
ll tot=0;
for (int j=0;j<=m;j++){
int l=1,r=0;
for (int k=1;k<=n;k++){
if (!lp[j][k]) continue;
while (l<lp[j][k]) mp[u[j][l++]]--;
while (r<rp[j][k]) mp[u[j][++r]]++;
tot+=mp[v[j][k]];
}
for (int k=l;k<=r;k++) mp[u[j][k]]=0;
}
int c=(tot<k); if (c) k-=tot;
int now=0;
for (int j=0;j<=m;j++)
for (int k=1;k<=n;k++){
v[j][k]^=c;
if (!num[v[j][k]]) now++,num[v[j][k]]=now,val[now]=v[j][k];
v[j][k]=num[v[j][k]];
}
for (int j=0;j<=m;j++)
for (int k=1;k<=n;k++)
if (num[u[j][k]]) u[j][k]=num[u[j][k]];
else u[j][k]=0;
while (now) num[val[now--]]=0;
ans=(ans<<1|c);
}
printf("%d\n",ans);
return 0;
}
```