差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:线性基 [2020/09/30 21:17]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:线性基 [2020/10/01 10:45] (当前版本)
jxm2001
@@ 行 23: / 行 23: @@
 先将极大无关组从大到小排好(这里大小是指向量代表的二进制数的大小)，依次决定是否选择该数。
-如果能保证当前面的选择相同时，选择该数一定比不选择该数的异或和大，再利用性质二，可以很容易得出第 $k$ 小异或和。
+如果能保证当前面的选择相同时，选择该数一定比不选择该数的异或和大。
+再利用性质二，可以很容易得出第 $k$ 小异或和。
 只要再将极大无关组的矩阵转化为行最简矩阵，便可以满足上述条件。
@@ 行 683: / 行 685: @@
 === 题解 ===
+考虑对每个 $r$，贪心维护区间 $[1,r]$ 的线性基每个位的数值和代表元位置。
+具体来说，对每个新插入的数，从高位到低位考虑是否可以将该值插入。
+如果该位置没有数则直接插入，否则如果该位置的代表元位置相对于插入数的位置偏左，则将该位置的代表元置换出来。
+对区间 $[l,r]$，考虑 $r$ 维护的线性基当前位的代表元位置是否不小于 $l$ 即可。时空间复杂度 $O((n+q)\log v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5;
+namespace LB{
+	const int MAXL=31;
+	int p1[MAXL],p2[MAXN][MAXL];
+	int pos1[MAXL],pos2[MAXN][MAXL];
+	void clear(){
+		mem(p1,0);mem(p2,0);
+		mem(pos1,0);mem(pos2,0);
+	}
+	void insert(int x,int pos){
+		int r=pos;
+		for(int i=MAXL-1;i>=0;i--){
+			if((x>>i)&1){
+				if(!p1[i]){
+					p1[i]=x;
+					pos1[i]=pos;
+					break;
+				}
+				else if(pos1[i]<pos){
+					swap(p1[i],x);
+					swap(pos1[i],pos);
+				}
+				x^=p1[i];
+			}
+		}
+		_for(i,0,MAXL){
+			p2[r][i]=p1[i];
+			pos2[r][i]=pos1[i];
+		}
+	}
+	LL query(int l,int r){
+		int ans=0;
+		for(int i=MAXL-1;i>=0;i--){
+			if(pos2[r][i]>=l&&(ans^p2[r][i])>ans)
+			ans^=p2[r][i];
+		}
+		return ans;
+	}
+};
+int main()
+{
+	int T=read_int();
+	while(T--){
+		int n=read_int(),q=read_int(),lastans=0;
+		LB::clear();
+		_rep(i,1,n)
+		LB::insert(read_int(),i);
+		while(q--){
+			int opt=read_int();
+			if(!opt){
+				int l=(read_int()^lastans)%n+1,r=(read_int()^lastans)%n+1;
+				if(l>r)swap(l,r);
+				enter(lastans=LB::query(l,r));
+			}
+			else
+			LB::insert(read_int()^lastans,++n);
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 练习题七 ====
+[[https://ac.nowcoder.com/acm/contest/884/B|2019牛客暑期多校训练营（第四场）B]]
+=== 题意 ===
+给定 $n$ 个集合和 $q$ 个询问，每个集合给定 $sz_i$ 个元素。
+每次询问对区间 $[l,r]$ 的每个集合是否都存在子集异或和为 $x$。
+=== 题解 ===
+考虑线段树求解，于是问题转化为如何维护两个线性基的交。
+线性空间 $v_1,v_2$ 的交 $v_3$ 仍为线性空间，仍然可以用线性基表示，且满足 $v_3$ 的线性基可以用 $v_1,v_2$ 的线性基表示。
+不妨记 $v_1$ 的线性基为 $a$，记 $v_2$ 的线性基为 $b$，记 $v_3$ 的线性基为 $c$。
+考虑初始空间为 $v_1$，然后依次将 $v_2$ 的线性基插入，如果插入出现线性相关，则有
+$$
+a_{x_1}\oplus a_{x_2}\oplus\cdots \oplus a_{x_{t_1}}\oplus b_{y_1}\oplus b_{y_2}\oplus\cdots \oplus b_{y_{t_2}}=b_i
+$$
+移项，得
+$$
+c=a_{x_1}\oplus a_{x_2}\oplus\cdots \oplus a_{x_{t_1}}=b_{y_1}\oplus b_{y_2}\oplus\cdots \oplus b_{y_{t_2}}\oplus b_i
+$$
+于是将新得到的 $c$ 插入 $v_3$ 即可。注意在插入 $v_2$ 过程中维护线性基每个位的 $v_1$ 空间的贡献。时间复杂度 $O((n+q)\log n\log v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5,MAXL=32;
+struct LB{
+	LL p[MAXL];
+	void insert(LL x){
+		for(int i=MAXL-1;i>=0;i--){
+			if((x>>i)&1){
+				if(p[i])
+				x^=p[i];
+				else
+				return p[i]=x,void();
+			}
+		}
+	}
+	bool query(LL x){
+		for(int i=MAXL-1;i>=0;i--){
+			if((x>>i)&1){
+				if(p[i])
+				x^=p[i];
+				else
+				return false;
+			}
+		}
+		return true;
+	}
+}a[MAXN],s[MAXN<<2];
+int lef[MAXN<<2],rig[MAXN<<2];
+void push_up(int k){
+	LB t=s[k<<1],v1=s[k<<1],v2=s[k<<1|1];
+	_for(i,0,MAXL){
+		if(v2.p[i]){
+			LL x=v2.p[i],y=0;
+			bool flag=true;
+			for(int j=MAXL-1;j>=0;j--){
+				if((x>>j)&1){
+					if(t.p[j]){
+						x^=t.p[j];
+						y^=v1.p[j];
+					}
+					else{
+						t.p[j]=x;
+						v1.p[j]=y;
+						flag=false;
+						break;
+					}
+				}
+			}
+			if(flag)
+			s[k].insert(y);
+		}
+	}
+}
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R;
+	int M=L+R>>1;
+	if(L==R)
+	return s[k]=a[M],void();
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+	push_up(k);
+}
+bool query(int k,int L,int R,LL x){
+	if(L>rig[k]||R<lef[k])
+	return true;
+	if(L<=lef[k]&&rig[k]<=R)
+	return s[k].query(x);
+	int M=L+R>>1;
+	return query(k<<1,L,R,x)&&query(k<<1|1,L,R,x);
+}
+int main()
+{
+	int n=read_int(),q=read_int();
+	_rep(i,1,n){
+		int cnt=read_int();
+		while(cnt--)
+		a[i].insert(read_LL());
+	}
+	build(1,1,n);
+	while(q--){
+		int l=read_int(),r=read_int();
+		if(query(1,l,r,read_LL()))
+		puts("YES");
+		else
+		puts("NO");
+	}
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具