牛客第四场 B xor —— 线性基的交 + 线段树

本文主要是介绍牛客第四场 B xor —— 线性基的交 + 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 个集合，每次查询一个值，该区间的所有集合都能用子集表示出这个值

解题思路：

    区间每个集合都能表示出一个值，就是线性基的交
    然后用线段树维护一下区间就完事了

核心：线性基求交的模板题

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
ll n, m, a[maxn][40];struct LB {ll cnt, d[35], p[35];LB() {cnt = 0;memset(d,0,sizeof(d));memset(p,0,sizeof(p));}void insert(ll x) {for(int i=32; ~i; i--)if(x & (1ll<<i)) {if(!d[i]) {d[i] = x;break;}x ^= d[i];}}bool check(ll x) {for(int i=32; ~i; i--)if(x & (1ll<<i)) {if(!d[i]) return false;x ^= d[i];}return true;}friend LB merge(const LB &A, const LB &B) {LB all, C, D;for(int i=32; ~i; i--) {all.d[i] = A.d[i];D.d[i] = 1ll << i;}for(int i=32; ~i; i--) {if(B.d[i]) {ll v = B.d[i], k = 0;bool can = true;for(int j=32; ~j; j--) {if(v & (1ll<<j)) {if(all.d[j]) {v ^= all.d[j];k ^= D.d[j];} else {can = false;all.d[j] = v;D.d[j] = k;break;}}}if(can) {v = 0;for(int j=32; ~j; j--)if(k & (1ll<<j))v ^= A.d[j];C.insert(v);}}}return C;}
} t[maxn<<2], s[maxn];void build(int l,int r,int rt) {if(l==r) {t[rt] = s[l];return ;}int m = l + r >> 1;build(lson);build(rson);t[rt] = merge(t[rt<<1], t[rt<<1|1]);
}bool query(int L,int R,int l,int r,int rt,int x) {if(L<=l && r<=R) return t[rt].check(x);int m = l + r >> 1, res = 1;if(L<=m) res = query(L,R,lson,x);if(R>m && res) res = query(L,R,rson,x);return res;
}int main() {scanf("%d%d", &n, &m);for(int i=1, num; i<=n; i++) {scanf("%d", &num);for(int j=1, x; j<=num; j++)scanf("%d", &x), s[i].insert(x);}build(1,n,1);while(m--) {ll l, r, x;scanf("%d%d%lld", &l, &r, &x);if(query(l,r,1,n,1,x)) puts("YES");else puts("NO");}
}

这篇关于牛客第四场 B xor —— 线性基的交 + 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---