G69 前缀线性基+贪心法 CF1100F Ivan and Burgers

#pragma optimize(2)
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=5e5+10,B=30;
template<typename T>void qr(T &x)
{
	x=0;char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c&15);
}
template<typename T>void qw(T x)
{
	if(x>=10)qw(x/10);
	putchar(x%10+'0');
}

int a[N], bas[N][B+1];int pos[N][B+1];
void ins(int x,int bass[],int poss[])
{
	int v=a[x];
	for(int i=B;i>=0;i--)if((v>>i)&1)
	{
		if(!bass[i]){bass[i]=v,poss[i]=x;return ;}
		if(poss[i]<x){swap(x,poss[i]);swap(v,bass[i]);}
		v^=bass[i];
	}
}

int main()
{
	int n;qr(n);
	memset(bas[0],0,sizeof(bas[0]));memset(pos[0],0,sizeof(pos[0]));
	for(int i=1;i<=n;i++)
	{
		qr(a[i]);
		memcpy(bas[i],bas[i-1],sizeof(bas[i]));
		memcpy(pos[i],pos[i-1],sizeof(pos[i]));
		ins(i,bas[i],pos[i]);
	}
	int q,l,r;qr(q);
	while(q--)
	{
		qr(l);qr(r);
		int ans=0;
		for(int i=B;i>=0;i--)if(pos[r][i]>=l)ans=max(ans,ans^bas[r][i]);
		qw(ans);
		putchar('\n');
	}
	return 0;
}

G69 前缀线性基+贪心法 CF1100F Ivan and Burgers

#pragma optimize(2)
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=5e5+10,B=30;
template<typename T>void qr(T &x)
{
	x=0;char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c&15);
}
template<typename T>void qw(T x)
{
	if(x>=10)qw(x/10);
	putchar(x%10+'0');
}

int a[N], bas[N][B+1];int pos[N][B+1];
void ins(int x,int bass[],int poss[])
{
	int v=a[x];
	for(int i=B;i>=0;i--)if((v>>i)&1)
	{
		if(!bass[i]){bass[i]=v,poss[i]=x;return ;}
		if(poss[i]<x){swap(x,poss[i]);swap(v,bass[i]);}
		v^=bass[i];
	}
}

int main()
{
	int n;qr(n);
	memset(bas[0],0,sizeof(bas[0]));memset(pos[0],0,sizeof(pos[0]));
	for(int i=1;i<=n;i++)
	{
		qr(a[i]);
		memcpy(bas[i],bas[i-1],sizeof(bas[i]));
		memcpy(pos[i],pos[i-1],sizeof(pos[i]));
		ins(i,bas[i],pos[i]);
	}
	int q,l,r;qr(q);
	while(q--)
	{
		qr(l);qr(r);
		int ans=0;
		for(int i=B;i>=0;i--)if(pos[r][i]>=l)ans=max(ans,ans^bas[r][i]);
		qw(ans);
		putchar('\n');
	}
	return 0;
}