CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:线性基 [2020/09/30 22:30]
jxm2001 [练习题六]
+++ 2020-2021:teams:legal_string:jxm2001:线性基 [2020/10/01 10:45] (当前版本)
jxm2001
@@ 行 23: / 行 23: @@
 先将极大无关组从大到小排好(这里大小是指向量代表的二进制数的大小)，依次决定是否选择该数。
-如果能保证当前面的选择相同时，选择该数一定比不选择该数的异或和大，再利用性质二，可以很容易得出第 $k$ 小异或和。
+如果能保证当前面的选择相同时，选择该数一定比不选择该数的异或和大。
+再利用性质二，可以很容易得出第 $k$ 小异或和。
 只要再将极大无关组的矩阵转化为行最简矩阵，便可以满足上述条件。
@@ 行 751: / 行 753: @@
 			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;

CVBB ACM Team

用户工具

站点工具

页面工具