Bucket of P (segment tree + linear basis)

Line segment tree + Linear base

link ：P4839 P Brother's bucket - Luogu | New ecology of computer science education (luogu.com.cn)

The question ： Insert data at a single point in the interval , Find the exclusive or sum of the largest subset of the interval .

Answer key ： Consider the combination of linear bases , Let's take another linear base log Take out the numbers and merge them into the first linear basis , Because numbers that can be synthesized from another linear basis , After merging this linear basis into the first linear basis , The first linear basis can also be combined into a second linear basis , Then we can synthesize those numbers through the second linear basis . Then the union of these linear bases can be maintained by using the line segment tree . Since the linear basis merging complexity is $log\ast log$, Line tree single point modification , The interval query complexity is $qlogn$, Then the overall complexity is $q\ast logn\ast lo{g}^{2}p$,q For the number of operations ,n Is the length of the sequence ,p Value range .

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
const int maxn=5e4+5;

int n,m,op,u,v,w;
struct node{
    
	int l,r,p[32];
	node():l(0),r(0){
    memset(p,0,sizeof(p));}
}t[maxn<<2];

void insert(node&t,int x)
{
    
	for(int i=31;i>=0;i--)
	{
    
		if(x>>i&1)
		{
    
			if(!t.p[i]){
    t.p[i]=x; break;}
			x^=t.p[i];
		}
	}
	return;
}

void pushup(int k)
{
    
	memcpy(t[k].p,t[k<<1].p,sizeof(t[k].p));
	for(int i=31;i>=0;i--)
	{
    
		insert(t[k],t[k<<1|1].p[i]);
	}
	return;
}

void build(int k,int l,int r)
{
    
	t[k].l=l,t[k].r=r;
	if(l==r)return;
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	return;
}

void update(int k,int pos,int w)
{
    
	int x=t[k].l,y=t[k].r;
	if(x==y){
    insert(t[k],w); return;}
	int mid=x+y>>1;
	if(pos<=mid)update(k<<1,pos,w);
	else update(k<<1|1,pos,w);
	pushup(k); return;
}

node query(int k,int l,int r)
{
    
	int x=t[k].l,y=t[k].r;
	if(l<=x&&y<=r)return t[k];
	int mid=x+y>>1,flag=0; node res;
	if(l<=mid)res=query(k<<1,l,r),flag=1;
	if(mid<r)
	{
    
		if(!flag)res=query(k<<1|1,l,r);
		else 
		{
    
			node q=query(k<<1|1,l,r); res.r=q.r;
			for(int i=31;i>=0;i--)insert(res,q.p[i]);
		}
	}
	return res;
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m,build(1,1,m);
	for(int i=1;i<=n;i++)
	{
    
		cin>>op>>u>>v;
		if(op==1)update(1,u,v);
		else
		{
    
			node q=query(1,u,v); int ans=0;
			for(int i=31;i>=0;i--)ans=max(ans,ans^q.p[i]);
			cout<<ans<<"\n";
		}
	}
	return 0;
}

You can find , This kind of merger is really right , Complexity is also correct . But consider , When we update, we merge from the bottom to the top , Each time, the number will be added to the original linear basis , No fewer numbers . So there is no need to merge , You only need to insert the traversed points when updating .

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
const int maxn=5e4+5;

int n,m,op,u,v,w;
struct node{
    
	int l,r,p[32];
	node():l(0),r(0){
    memset(p,0,sizeof(p));}
}t[maxn<<2];

void insert(node&t,int x)
{
    
	for(int i=31;i>=0;i--)
	{
    
		if(x>>i&1)
		{
    
			if(!t.p[i]){
    t.p[i]=x; break;}
			x^=t.p[i];
		}
	}
	return;
}

void build(int k,int l,int r)
{
    
	t[k].l=l,t[k].r=r;
	if(l==r)return;
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	return;
}

void update(int k,int pos,int w)
{
    
	int x=t[k].l,y=t[k].r; insert(t[k],w);
	if(x==y)return;
	int mid=x+y>>1;
	if(pos<=mid)update(k<<1,pos,w);
	else update(k<<1|1,pos,w);
	return;
}

void query(node&q,int k,int l,int r)
{
    
	int x=t[k].l,y=t[k].r;
	if(l<=x&&y<=r)
	{
    
		for(int i=31;i>=0;i--)insert(q,t[k].p[i]);
		return;
	}
	int mid=x+y>>1;
	if(l<=mid)query(q,k<<1,l,r);
	if(mid<r)query(q,k<<1|1,l,r);
	return;
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m,build(1,1,m);
	for(int i=1;i<=n;i++)
	{
    
		cin>>op>>u>>v;
		if(op==1)update(1,u,v);
		else
		{
    
			node q; query(q,1,u,v); int ans=0;
			for(int i=31;i>=0;i--)ans=max(ans,ans^q.p[i]);
			cout<<ans<<"\n";
		}
	}
	return 0;
}

Query operation small optimization ： It is found that it takes too much time to re create the structure every time each point is queried . Then create one initially and insert it slowly .