线性基（贪心版）

线性基（贪心版）：能够解决 1.求所有最大异或和 2.查询x能否被子集异或表示 3.合并线性基

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
using pii=pair<int,int>;
const int mod=998244353;
const int maxn=5e5+5;
#define lowbit(x) (x&(-x))
#define vc vector<int>
#define endl '\n'

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) write(x / 10);  
	putchar(x % 10 + '0');
}

const int maxbit=60;
int b[maxbit+5];

//插入
void insert(int x)
{
	for (int i=maxbit;i>=0;i--)
	{
		if ((x>>i)&1)
		{
			if (!b[i])
			{
				b[i]=x;
				return ;
			}
			x^=b[i];
		}
	}
}

//求最大异或和
int getsum()
{
	int ans=0;
	for (int i=maxbit;i>=0;i--)
	{
		int t=ans^b[i];
		if (ans<t)
		{
			ans=t;
		}
	}
	return ans;
}


//查询x能否被子集异或表示
bool check(long long x){
	for(int i=maxbit;i>=0;i--){
		if((x>>i)&1){
			if(!b[i]) return 0;
			x^=b[i];
		}
	}
	return 1;
}

//合并另一个线性基
void merge(long long *other){
	for(int i=0;i<=maxbit;i++){
		if(other[i]) insert(other[i]);
	}
}

void solve()
{

}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t=1;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

insert(x) 插入一个数 时间复杂度：O（maxbit）。

getsum( ) 求最大异或和 时间复杂度：O（maxbit）。

check(x) 判断 x 能否被异或表示: O(maxbit)。

merge(other) 合并另一套线性基: O(maxbit²)