题目链接：https://ac.nowcoder.com/acm/contest/884/B
题目大意：
有n个集合，每个集合有若干元素，一个集合i能表示x，当且仅当存在一个集合i的子集合，这里面的元素异或值为x。
有m个询问：每个为x,l,r，如果任意一个集合i (i在[l,r])都能表示x，输出YES，否则输出NO。
解题报告：对于每一个集合建立线性基，然后用线段树维护，线段树叶子结点表示这个第i个集合的线性基，非叶子结点等于两个儿子结点的线性基的交。
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=50002; 5 struct node { 6 ll p[33]; 7 void init() { 8 memset(p,0,sizeof(p)); 9 } 10 void ins(ll x) { 11 for(int i=32;~i;i--) { 12 if((x>>i)&1) 13 if(p[i]) x^=p[i]; 14 else { 15 p[i]=x; 16 return ; 17 } 18 } 19 } 20 bool check(ll x) { 21 for(int i=32;~i;i--) { 22 if((x>>i)&1) { 23 if(p[i]) x^=p[i]; 24 else return false; 25 } 26 } 27 return true; 28 } 29 node inter(node k) { ///求两线性基的交 30 node res,v2=k; 31 res.init(); 32 for(int i=0;i<=32;i++) { 33 if(p[i]) { ///考虑将v1.p[i]插入合并后的线性基 34 ll now=0,x=p[i]; 35 bool flag=false; 36 for(int j=32;~j;j--) { 37 if((x>>j)&1) { 38 if(k.p[j]) { 39 x^=k.p[j]; 40 now^=v2.p[j]; 41 } 42 else { ///不是线性基的交 43 k.p[j]=x; 44 v2.p[j]=now; 45 flag=true; 46 break; 47 } 48 } 49 } 50 if(!flag) res.p[i]=now; 51 } 52 } 53 return res; 54 } 55 }wtz[maxn<<2]; 56 vector<ll>v[maxn]; 57 void build(int k,int l,int r) { 58 wtz[k].init(); 59 if(l==r) { 60 int sz=v[l].size(); 61 for(int i=0;i<sz;i++) 62 wtz[k].ins(v[l][i]); ///叶子结点插入线性基 63 return ; 64 } 65 int mid=(l+r)>>1; 66 build(k<<1,l,mid); 67 build(k<<1|1,mid+1,r); 68 wtz[k]=wtz[k<<1].inter(wtz[k<<1|1]); ///非叶子结点等于两个线性基的交 69 } 70 bool query(int k,int l,int r,int a,int b,ll x) { 71 if(a<=l&&r<=b) 72 return wtz[k].check(x); 73 int mid=(l+r)>>1; 74 if(a<=mid&&!query(k<<1,l,mid,a,b,x)) return false; 75 if(mid<b&&!query(k<<1|1,mid+1,r,a,b,x)) return false; 76 return true; 77 } 78 int main() 79 { 80 int n,m,sz; 81 ll x; 82 scanf("%d%d",&n,&m); 83 for(int i=1;i<=n;i++) { 84 scanf("%d",&sz); 85 for(int j=1;j<=sz;j++) { 86 scanf("%lld",&x); 87 v[i].push_back(x); 88 } 89 } 90 build(1,1,n); 91 int l,r; 92 for(int i=1;i<=m;i++) { 93 scanf("%d%d%lld",&l,&r,&x); 94 if(query(1,1,n,l,r,x)) printf("YES "); 95 else printf("NO "); 96 } 97 return 0; 98 }
1 #include<bits/stdc++.h> 2 #define numm ch-48 3 #define pd putchar(' ') 4 #define pn putchar(' ') 5 #define pb push_back 6 #define fi first 7 #define se second 8 #define fre1 freopen("1.txt","r",stdin) 9 #define fre2 freopen("2.txt","w",stdout) 10 #define debug(args...) cout<<#args<<"->"<<args<<" "; 11 using namespace std; 12 template <typename T> 13 void read(T &res) { 14 bool flag=false;char ch; 15 while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true); 16 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm); 17 flag&&(res=-res); 18 } 19 template <typename T> 20 void write(T x) { 21 if(x<0) putchar('-'),x=-x; 22 if(x>9) write(x/10); 23 putchar(x%10+'0'); 24 } 25 typedef long long ll; 26 typedef unsigned long long ull; 27 const int maxn=50010; 28 const int maxm=505; 29 const int mod=1e9+7; 30 const int inv2=500000004; 31 const int N=32; 32 int sz; 33 ll x; 34 struct node { 35 ll p[N+2]; 36 void init() { 37 for(int i=N;~i;i--) 38 p[i]=0; 39 } 40 void ins(ll x) { 41 for(int i=N;~i;i--) { 42 if(x&(1LL<<i)) 43 if(p[i]) x^=p[i]; 44 else { 45 p[i]=x; 46 return ; 47 } 48 } 49 } 50 bool check(ll x) { 51 for(int i=N;~i;i--) { 52 if(x&(1LL<<i)) { 53 if(p[i]) x^=p[i]; 54 else return false; 55 } 56 } 57 return true; 58 } 59 ll& operator [](int x) { 60 return p[x]; 61 } 62 }wtz[maxn<<2],temp,v1; 63 void inter(node &a,node &b,node &c) { 64 temp=v1=a; 65 for(int i=N;~i;i--) { 66 if(b[i]) { ///考虑将b[i]插入合并后的线性基 67 ll now=0,x=b[i]; 68 bool flag=false; 69 for(int j=N;~j;j--) { 70 if(x&(1LL<<j)) { 71 if(temp[j]) { 72 x^=temp[j]; 73 now^=v1[j]; 74 } 75 else { ///不是线性基的交 76 temp[j]=x; 77 v1[j]=now; 78 flag=true; 79 break; 80 } 81 } 82 } 83 if(!flag) c.ins(now); 84 } 85 } 86 } 87 void build(int k,int l,int r) { 88 if(l==r) { 89 read(sz); 90 while(sz--) { 91 read(x); 92 wtz[k].ins(x); ///叶子结点插入线性基 93 } 94 return ; 95 } 96 int mid=(l+r)>>1; 97 build(k<<1,l,mid); 98 build(k<<1|1,mid+1,r); 99 inter(wtz[k<<1],wtz[k<<1|1],wtz[k]); ///非叶子结点等于两个线性基的交 100 } 101 bool query(int k,int l,int r,int a,int b,ll x) { 102 if(l>=a&&r<=b) 103 return wtz[k].check(x); 104 int mid=(l+r)>>1; 105 if(a<=mid&&!query(k<<1,l,mid,a,b,x)) return false; 106 if(mid<b&&!query(k<<1|1,mid+1,r,a,b,x)) return false; 107 return true; 108 } 109 int main() 110 { 111 // #define local 112 #ifdef local 113 fre1; 114 // fre2; 115 #endif // local 116 int n,m; 117 read(n),read(m); 118 build(1,1,n); 119 int l,r; 120 while(m--) { 121 read(l),read(r),read(x); 122 if(query(1,1,n,l,r,x)) puts("YES"); 123 else puts("NO"); 124 } 125 return 0; 126 }