原理
坑。
例题
P哥的桶
首先有一道很水的例题。
题意
一共有 n 个数组，可以向某一个数组里增加一个数，或者询问区间内所有数组里数组可能的最大异或和。
思路
线性基套上一个线段树，可以学习一下基本插入和查询操作。
#include
#define maxn 50001
#define maxl 32
#define ll long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
using namespace std;
struct LB{
ll a[maxl+1];
void reset(){
memset(a,0,sizeof(a));
}
void insert(ll t){
for (int j=maxl;j>=0;j--){
if (!t) return;
if (!(t&(1ll<k||rR) return;
if (l>=L&&r<=R){merge(temp,tree[p]);return;}
query(l,mid,L,R,ls),query(mid+1,r,L,R,rs);
}
int main(){
ios::sync_with_stdio(false);
int n,m,op,k;ll v;
cin>>m>>n;
while(m--){
cin>>op>>k>>v;
if (op==1) update(1,n,k,v,1);
else temp.reset(),query(1,n,k,v,1),cout< 最大XOR和路径
题意
在可能有重边自环的有向图里寻找一条从 1 到 $N$ 的路径，可以重复经过某些点或边，最大化经过的点权 XOR和。
思路
首先我们考虑任意一条从 1 到 $N$ 的简单路径。
由于可以重复经过一些点，也就是我们可以向外走一个环再回来。
发现从链上一点到环之间的路径经过两次对答案没有贡献，所以我们可以预处理出所有环的答案丢到线性基里贪心选取。
这种做法对一开始选取的简单路径没有要求，因为假设存在更优的路径，它和当前的这条路径形成的环也被加进了线性基里，如果选取了这个环，就相当于走了另外一条更优的路径。
代码
#include
#define ll long long
#define maxn 50001
#define maxl 63
using namespace std;
struct LB{
ll a[maxl+1];
void insert(ll t){
for (int j=maxl;j>=0;j--){
if (!t) return;
if (!(t&(1ll<=0;i--)
if((x^a[i])>x) x^=a[i];
return x;
}
}K;
struct Edge{
int to,next;
ll val;
Edge(int a=0,int b=0,ll c=0){
to=a,next=b,val=c;
}
}l[200100];
int head[maxn],vis[maxn],cnt,n,m;
ll dis[maxn];
void Add(int x,int y,ll z){
l[++cnt]=Edge(y,head[x],z);
head[x]=cnt;
}
void Dfs(int x,int f){
vis[x]=1;
for (int i=head[x];i;i=l[i].next){
int v=l[i].to;
if (v==f) continue;
if (!vis[v]) dis[v]=dis[x]^l[i].val,Dfs(v,x);
else K.insert(dis[x]^dis[v]^l[i].val);
}
}
int main(){
ios::sync_with_stdio(false);
int n,m;cin>>n>>m;
for (int i=1;i<=m;i++){
int x,y;
ll z;
cin>>x>>y>>z;
Add(x,y,z);
Add(y,x,z);
}
Dfs(1,0);
cout< 致谢
我的板子是从 Menci 那里学来的，感谢学长 qwq。