Reincarnation

正因为梦易碎，才格外美好。

线性基

发表于 分类于 ，
本文字数： 29k 阅读时长 ≈ 26 分钟

擦肩而过的朋友，结伴而行的路人。

线性基

线性基是线性代数定义下的基底。一般而言，我们都拿二维平面向量来作比较。在高中数学的学习中，我们知道如何判断一组向量 是否可以作为基底，当且仅当 。通俗来讲，就是给所有的 一个系数，使得 组合能够表示这个平面的所有向量。

那么同理，若现在存在一个向量集合 ，以及另一个向量集合 。如果 能够通过线性组合得到 ，那么称 为 的线性基。请注意，这里 必须是所有满足条件的集合中最小的。

线性基可能不唯一，在线性代数中会使用，而 中大多情况使用的是异或线性基，也就是将线性组合换成按位异或，所有的 能够通过若干个 异或出，则 是 的异或线性基。但无论如何 都是最小的。

构造 & 实现

很显然， 肯定是一个合法解，但不一定是最优解，但我们可以沿袭这个思路，每次将 插入到 中构造线性基。

对于当前已经得到的线性基集合 ，如果接下来要插入的数 已经能够被 中的元素通过按位异或得出，那么 一定就不需要被插入到线性基中，否则会使元素赘余。否则，意味着 无法被异或出，那显然就必须将 插入到线性基中。

为了保证元素个数最少，我们要求线性基中任意两个元素的二进制最高位不能相同，这样的话，可以保证我们的集合大小在 以内，是一个非常不错的成绩。

考虑使这个不错的复杂度正确性成立，这意味着我们插入的元素一定是 的元素或其元素与已经在线性基集合中的元素的异或和，这样正确性就有了。

考虑实现，用 表示最高位为 的线性基内的元素，显然唯一（当然这个唯一取决于插入顺序），对于当然需要插入的 ，如果在第 为 为 ，那么令 ，直到遇到一个 使得 而 ，那么使 ，插入结束。

参考实现
 
1
2
3
4
5
6
7
8
9
10
ll Set[70];  //long long不过64位
inline void insert(ll x)
{
  for(int i=63;~i;--i)
    if(x>>i&1)
    {
      if(Set[i]) x^=Set[i];
      else return Set[i]=x,void();
    }
}

性质

  • 异或线性基不存在子集异或和为 ；
  • 线性基不存在两个不同子集异或和相同；
  • 线性基集合中任意元素的最高位不同；

例题 & 运用

最大异或和

题目简介

题目名称：线性基
题目来源：洛谷
评测链接：https://www.luogu.com.cn/problem/P3812

形式化题意：给定 个数 ，求选择一些 并最大化异或和。

数据范围：

首先考虑对 建出线性基 ，如果我们要求最大异或和，显然秉承一种高位最优，低位随意的想法，也就是从高向低扫描线性基，如果当前位 存在线性基，那我们让答案异或上 ，这样我们就保证了第 位为 ，而低位的改变并不会影响答案，因为第 位是最高的 位，就算 位全部为 ，也比第 位为 小。

而对于之后的低位，我们只需要在当前答案上取 即可。时间复杂度 。

听说这道题还有一个 的鬼畜做法，用 优化，前半段子集求和建状压 树，后半段暴力枚举，显然这不是我们本节提及的重点。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// ----- Eternally question-----
// Problem: P3812 【模板】线性基
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3812
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-08-28 08:37:23
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=60;
int N;
ll val[MAXN];
struct Basis
{
	ll Set[MAXN];
	int Tot;
	inline void init(){ std::memset(Set,0,sizeof(Set)); }
	inline void insert(ll x)
	{
		for(int i=50;~i;--i)
			if(x>>i&1)
			{
				if(Set[i]) x^=Set[i];
				else return Set[i]=x,++Tot,void();
			}
	}
	inline ll getMax()
	{
		ll res=0;
		for(int i=50;~i;--i) checkMax(res,res^Set[i]);
		return res;
	}
}Set;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(val[i]),Set.insert(val[i]);
	write(Set.getMax());
	return 0;
}
/*

*/

子集异或和计数

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/895/C

形式化题意：给定一个长度为 的序列 ，求出 的非空子集 满足 中所有元素的乘积为完全平方数。求出集合 的个数。对 取模。

数据范围：

如果多个数的乘积为完全平方数，从质因子的方向考虑，那么所有的质因子的出现次数都为偶数次。考虑到 ，质因子只有 个，所以可以直接状压，所以可以做状压 ，这里不多赘述。

但实际上，如果一个数要求出现次数为偶数，那一定有 出现，我们将每个 拆分成质因子状压形式，实际上就是求出所有子集异或和为 的个数。

根据线性基的定义，我们将 分成了两个集合 满足 ，而 为线性基集合。此时保证了去除 中任意子集，都存在一个 的子集异或和与之相等，且不重不漏。

所以，要求异或和为 的子集，实际上就是 的子集，答案就是 。时间复杂度 。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// ----- Eternally question-----
// Problem: C. Square Subsets
// Contest: Codeforces - Codeforces Round 448 (Div. 2)
// URL: https://codeforces.com/problemset/problem/895/C
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2023-08-28 08:57:05
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXS=1<<19|10,MAXM=20;
const int Mod=1e9+7;
int N,val[MAXN];
int Set[MAXN],Tot,ans;
int pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
inline void insert(int x)
{
	for(int i=30;~i;--i)
		if(x>>i&1)
		{
			if(Set[i]) x^=Set[i];
			else return Set[i]=x,++Tot,void();
		}
}
inline bool check(int x)
{
	for(int i=30;~i;--i)
		if(x>>i&1)
		{
			if(Set[i]) x^=Set[i];
			else return 0;
		}
	return 1;
}
inline int qPow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=(ll)a*a%Mod) (b&1)&&(res=(ll)res*a%Mod);
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i)
	{
		read(val[i]);
		int x=0;
		for(int j=1;j<=19;++j)
		{
			x<<=1;
			while(!(val[i]%pri[j])) x^=1,val[i]/=pri[j];
		}
		insert(x);
	}
	write((qPow(2,N-Tot)+Mod-1)%Mod);
	return 0;
}
/*

*/

子集异或和计数 II

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/959/F

形式化题意：给定 个数 以及 次询问，每次询问 中有多少个子序列异或和为 ，对 取模。

数据范围：

上面已经说到，异或和为 的子集数为 ，那我们把询问离线从 作扫描线，判断当前 是否能被异或出，那么答案要么为 要么为 。

判断与插入同理，只是如果当前需要插入了则无解，而当 了则有解。

时间复杂度 。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// ----- Eternally question-----
// Problem: F. Mahmoud and Ehab and yet another xor task
// Contest: Codeforces - Codeforces Round 473 (Div. 2)
// URL: https://codeforces.com/problemset/problem/959/F
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-08-28 09:30:38
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=1e5+10;
const int Mod=1e9+7;
int N,Q,val[MAXN];
int Set[MAXN],Tot,ans[MAXN];
std::vector<Pir>Qr[MAXN];
inline int qPow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=(ll)a*a%Mod) (b&1)&&(res=(ll)res*a%Mod);
	return res;
}
inline void insert(int x)
{
	for(int i=20;~i;--i)
		if(x>>i&1)
		{
			if(Set[i]) x^=Set[i];
			else return Set[i]=x,++Tot,void();
		}
}
inline bool check(int x)
{
	for(int i=20;~i;--i)
		if(x>>i&1)
		{
			if(Set[i]) x^=Set[i];
			else return 0;
		}
	return 1;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1;i<=N;++i) read(val[i]);
	for(int i=1,ql,qx;i<=Q;++i) read(ql,qx),Qr[ql].emplace_back(Mkr(qx,i));
	for(int i=1;i<=N;++i)
	{
		insert(val[i]);
		for(auto q:Qr[i]) if(check(q.fir)) ans[q.sec]=qPow(2,i-Tot);
	}
	for(int i=1;i<=Q;++i) write(ans[i],'\n');
	return 0;
}
/*

*/

带标号线性基

题目简介

题目名称：元素
题目来源：

评测链接：https://www.luogu.com.cn/problem/P4570

形式化题意：给定 个物品，其贡献是一个二元组 ，你需要指定一个物品集合 ，要求 中任意子集 的异或和不为 ，并最大化 的和。

数据范围：

考虑这个 一定是原序列对 的线性基，因为线性基中有一个性质就是不存在异或和为 的子集。然后考虑求最大化 的线性基，我们贪心的想，直接按照 排序后插入线性基即可。

然后讲带标号，实际就是记录一个当前位的线性基对应的原序列编号，开个数组 记一下就可以了。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// ----- Eternally question-----
// Problem: P4570 [BJWC2011] 元素
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4570
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-08-28 09:51:57
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e3+10;
int N,Id[70];
struct Stone
{
	ll ser;
	int val;
	bool operator<(const Stone &x) const
	{ return val>x.val; }
}St[MAXN];
ll Set[70];
inline void insert(ll x,int id)
{
	for(int i=63;~i;--i)
		if(x>>i&1)
		{
			if(Set[i]) x^=Set[i];
			else return Set[i]=x,Id[i]=id,void();
		}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(St[i].ser,St[i].val);
	std::sort(St+1,St+N+1);
	for(int i=1;i<=N;++i) insert(St[i].ser,i);
	ll ans=0;
	for(int i=0;i<=63;++i) ans+=St[Id[i]].val;
	write(ans);
	return 0;
}
/*

*/

线性基合并

题目简介

题目名称： 歌的桶

题目来源：洛谷
评测链接：https://www.luogu.com.cn/problem/P4839

形式化题意：给定 个集合，维护 次操作：

  • 向第 个集合中插入 ；
  • 求第 到 个集合的并的子集的最大异或和。

数据范围：

发现是一个单点修区间查的形式，所以多半可以用线段树维护。问题在于怎么维护，我们可以考虑在每个线段树结点上开一个线性基，然后每次查询把需要用到的 个线性基合并后求答案。

线性基的合并非常暴力，合并 ，就直接开一个空的线性基 ，然后将 中所有元素插入到 中即可，时间复杂度 。然后套到线段树上即可，时间复杂度 ，常数有点小大，剪剪枝卡卡常开个 能过。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// ----- Eternally question-----
// Problem: P4839 P 哥的桶
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4839
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-08-28 10:21:59
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e4+10;
int N,Q;
struct Basis
{
	int Set[33];
	Basis(){ std::memset(Set,0,sizeof(Set)); }
	inline void build(){ std::memset(Set,0,sizeof(Set)); }
	inline void insert(int x)
	{
		if(!x) return ;
		for(int i=31;~i;--i)
			if(x>>i&1)
			{
				if(Set[i]) x^=Set[i];
				else return Set[i]=x,void();
			}
	}
	inline int getmax()
	{
		int res=0;
		for(int i=31;~i;--i) checkMax(res,res^Set[i]);
		return res;
	}
};
inline Basis merge(Basis a,Basis b)
{
	Basis c;
	for(int i=0;i<=31;++i) c.insert(a.Set[i]),c.insert(b.Set[i]);
	return c;
}
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{
	int l,r;
	Basis val;
}Tr[MAXN<<2];
inline void pushUp(int p)
{ Tr[p].val=merge(Tr[ls].val,Tr[rs].val); }
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return Tr[p].val.build();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void modifyIns(int p,int x,int v)
{
	if(Tr[p].l==Tr[p].r) return Tr[p].val.insert(v);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	x<=mid?modifyIns(ls,x,v):modifyIns(rs,x,v);
	pushUp(p);
}
Basis querySet(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
	int mid=(Tr[p].l+Tr[p].r)>>1;
	Basis res;
	if(l<=mid) res=querySet(ls,l,r);
	if(mid<r) res=merge(res,querySet(rs,l,r));
	return res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Q,N);
	build(1,1,N);
	for(int opt,ql,qr;Q--;)
	{
		read(opt,ql,qr);
		if(opt==1) modifyIns(1,ql,qr);
		else write(querySet(1,ql,qr).getmax(),'\n');
	}
	return 0;
}
/*

*/

前缀线性基

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/1100/F

形式化题意：给定 个数 ，以及 次询问，每次询问 子集的最大异或和。

数据范围：

直接上手线段树合并线性基，你发现 支 根本跑不起来。但有一个致命的性质，就是这道题不带修。

于是就有人上手猫树分治合并线性基，可以做到 ，卡常可过，当然还有更多玄学方法，用 lxl 分块 表也可以做到这个复杂度。但我们现在要讲一个单 的做法。

前缀线性基，可以在 的时间内解决静态区间最值问题。

考虑带标号的形式，我们对每一位记录 表示当前位的线性基对应序列的哪一位，然后我们贪心的使线性基合法的前提下 最大，在插入的中途与原先的元素比较，如果更大则交换。

而对于询问，只需要考虑所有 的线性基，这就是由 内的元素构成的区间线性基。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// ----- Eternally question-----
// Problem: F. Ivan and Burgers
// Contest: Codeforces - Codeforces Round 532 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1100/F
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-08-28 10:52:56
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10;
int N,Q;
struct Basis
{
	int Set[30],Pos[30];
	Basis(){ std::memset(Set,0,sizeof(Set)); }
	inline void build(){ std::memset(Set,0,sizeof(Set)); }
	inline void insert(int x,int p)
	{
		if(!x) return ;
		for(int i=24;~i;--i)
			if(x>>i&1)
			{
				if(!Set[i]) return Set[i]=x,Pos[i]=p,void();
				else if(p>Pos[i]) std::swap(Set[i],x),std::swap(Pos[i],p);
				x^=Set[i];
			}
	}
	inline int getmax(int l)
	{
		int res=0;
		for(int i=24;~i;--i) if(Pos[i]>=l) checkMax(res,res^Set[i]);
		return res;
	}
}a[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	a[0].build();
	for(int i=1,x;i<=N;++i)
	{
		read(x);a[i]=a[i-1];
		a[i].insert(x,i);
	}
	read(Q);
	for(int ql,qr;Q--;)
	{
		read(ql,qr);
		write(a[qr].getmax(ql),'\n');
	}
	return 0;
}
/*

*/

线性基合并 II

题目简介

题目名称：无力回天

题目来源：

评测链接：https://www.luogu.com.cn/problem/P5607

形式化题意：给定一个长度为 的序列，以及 次操作：

  • 对区间 执行 ；
  • 选取区间 内的一个子序列求与 的最大异或和。

数据范围：

正解可以看 做题记录，这里就不写第二遍了。

因为异或有一个优美的差分性子（），而涉及到区间操作的时候，其一就是将其差分转化为单点，其二就是考虑区间长度的奇偶性，这样要么该区间和不变，要么区间只会异或一次 ，当然，两种情况要视题目而定。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
// ----- Eternally question-----
// Problem: P5607 [Ynoi2013] 无力回天 NOI2017
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5607
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-08-28 14:46:50
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e4+10,MAXS=34;
int N,Q,val[MAXN];
struct Basis
{
	int Set[MAXS];
	Basis(){ std::memset(Set,0,sizeof(Set)); }
	int operator[](const int &x){ return Set[x]; }
	inline void init(){ std::memset(Set,0,sizeof(Set)); }
	inline void insert(int x)
	{
		if(!x) return ;
		for(int i=31;~i;--i)
			if(x>>i&1)
			{
				if(Set[i]) x^=Set[i];
				else return Set[i]=x,void();
			}
	}
};
inline Basis merge(Basis a,Basis b)
{
	Basis c;
	for(int i=0;i<=31;++i) c.insert(a[i]),c.insert(b[i]);
	return c;
}
struct Segment
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct St
	{
		int l,r;
		Basis val;
	}Tr[MAXN<<2];
	inline void pushUp(int p){ Tr[p].val=merge(Tr[ls].val,Tr[rs].val); }
	void build(int p,int l,int r)
	{
		Tr[p].l=l,Tr[p].r=r;
		for(int i=l;i<=r;++i) Tr[p].val.insert(val[i]);
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		pushUp(p);
	}
	void modifyX(int p,int x,int v)
	{
		if(Tr[p].l==Tr[p].r)
		{
			Tr[p].val.init();
			Tr[p].val.insert((val[x]^=v));
			return ;
		}
		int mid=(Tr[p].l+Tr[p].r)>>1;
		x<=mid?modifyX(ls,x,v):modifyX(rs,x,v);
		pushUp(p);
	}
	Basis querySet(int p,int l,int r)
	{
		if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
		int mid=(Tr[p].l+Tr[p].r)>>1;
		Basis res;
		if(l<=mid) res=querySet(ls,l,r);
		if(mid<r) res=merge(res,querySet(rs,l,r));
		return res;
	}
}Tr;
struct BIT
{
	int Tre[MAXN],Siz;
	inline int lowbit(int x){ return x&(-x); }
	inline void build(int n){ Siz=n;for(int i=0;i<=n;++i) Tre[i]=0; }
	inline void add(int x,int v){ for(;x<=Siz;x+=lowbit(x)) Tre[x]^=v; }
	inline int query(int x)
	{
		int res=0;
		for(;x;x-=lowbit(x)) res^=Tre[x];
		return res;
	}
}Tre;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);Tre.build(N);
	for(int i=1;i<=N;++i) read(val[i]);
	for(int i=N;i>=2;--i) val[i]^=val[i-1];
	for(int i=1;i<=N;++i) Tre.add(i,val[i]);
	Tr.build(1,1,N);
	for(int opt,ql,qr,qv;Q--;)
	{
		read(opt,ql,qr,qv);
		if(opt==1)
		{
			Tre.add(ql,qv);Tr.modifyX(1,ql,qv);
			if(qr<N) Tre.add(qr+1,qv),Tr.modifyX(1,qr+1,qv);
		}
		else
		{
			int al=Tre.query(ql);
			if(ql==qr) write(std::max(qv,al^qv),'\n');
			else
			{
				Basis cur=Tr.querySet(1,ql+1,qr);
				cur.insert(al);
				for(int i=31;~i;--i) checkMax(qv,qv^cur[i]);
				write(qv,'\n');
			}
		}
	}
	return 0;
}
/*

*/

线性基合并 III

题目简介

题目名称：幸运数字
题目来源：四川省选 第一天第二题
评测链接：https://www.luogu.com.cn/problem/P3292

形式化题意：给定一棵 个结点的树，每个结点有一个权值 ，每次询问一条路径 上结点组成的权值集合的子集最大异或和。

数据范围：

时空限制：

大家好，我是大常数暴力选手，所以我用树剖过了这道题。

考虑最暴力的方式就是通过树剖维护线段树，然后线段树结点维护线性基，可以做到 ，有一说一我都不知道怎么过的，好像是后来开大了时限，省选场上是过不了的。

然后考虑并不带修，所以用倍增代替树剖可以优化掉查询的一支 。

离线拆贡献用猫树分治合并可以做到 。但空间较大，码量也不小。

在线做法有维护深度前缀线性基，也可以做到 。

写的树剖，其它做法居然还要动脑子，真的大受震撼（不是。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
// ----- Eternally question-----
// Problem: P3292 [SCOI2016] 幸运数字
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3292
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-08-28 15:35:41
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e4+10,MAXS=70;
int N,Q;
ll val[MAXN];
struct G
{ int next,to; }Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Fa[MAXN],Dep[MAXN],Siz[MAXN],Son[MAXN];
void dfsTree(int x,int last)
{
	Fa[x]=last,Dep[x]=Dep[last]+1,Siz[x]=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dfsTree(v,x);
		Siz[x]+=Siz[v];
		if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
	}
}
int Top[MAXN],Dfn[MAXN],Bck[MAXN],Cnt;
void dfsChain(int x,int topf)
{
	Top[x]=topf,Dfn[x]=++Cnt;
	Bck[Cnt]=x;
	if(!Son[x]) return ;
	dfsChain(Son[x],topf);
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
		dfsChain(v,v);
	}
}
struct Basis
{
	ll Set[MAXS];
	Basis(){ std::memset(Set,0,sizeof(Set)); }
	ll operator[](const int &x){ return Set[x]; }
	inline void build(){ std::memset(Set,0,sizeof(Set)); }
	inline void insert(ll x)
	{
		if(!x) return ;
		for(int i=63;~i;--i)
			if(x>>i&1)
			{
				if(Set[i]) x^=Set[i];
				else return Set[i]=x,void();
			}
	}
};
inline Basis merge(Basis a,Basis b)
{
	Basis c;
	for(int i=0;i<=63;++i) c.insert(a[i]),c.insert(b[i]);
	return c;
}
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{
	int l,r;
	Basis val;
}Tr[MAXN<<2];
inline void pushUp(int p)
{ Tr[p].val=merge(Tr[ls].val,Tr[rs].val); }
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return Tr[p].val.insert(val[Bck[l]]),void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
Basis querySet(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
	int mid=(Tr[p].l+Tr[p].r)>>1;
	Basis res;
	if(l<=mid) res=querySet(ls,l,r);
	if(mid<r) res=merge(res,querySet(rs,l,r));
	return res;
}
inline Basis getPath(int x,int y)
{
	Basis res;
	while(Top[x]!=Top[y])
	{
		if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
		res=merge(res,querySet(1,Dfn[Top[x]],Dfn[x]));
		x=Fa[Top[x]];
	}
	if(Dep[x]>Dep[y]) std::swap(x,y);
	return merge(res,querySet(1,Dfn[x],Dfn[y]));
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1;i<=N;++i) read(val[i]);
	for(int i=2,u,v;i<=N;++i) read(u,v),addEdge(u,v);
	dfsTree(1,0),dfsChain(1,1);
	build(1,1,N);
	for(int u,v;Q--;)
	{
		read(u,v);
		Basis ret=getPath(u,v);
		ll ans=0;
		for(int i=63;~i;--i) checkMax(ans,ans^ret[i]);
		write(ans,'\n');
	}
	return 0;
}
/*

*/
相关文章