[线性基][线段树][模板] 牛客多校第四场 B xor

题目链接

题意：

$n$ 个集合，每个集合最多32个unsigned int范围的整数， $m$ 个询问，每次问下标在 $[l,r]$ 之间的集合能否表示出 $x$ 。数据范围 $1\le n,m\le 50000$，每个数字都在 unsigned int 以内。

题解：

线段树维护线性基即可。学习了一发板子。

wa点：

• 求交写成求并集了。。判断错误
• 学习了一发线性基求交集和check是否可以张成的板子。。。

#include<bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
//typedef unsigned int ll;
const int maxn=5e4+5;
//const double pi=acos(-1.0);
 
const int MAXL =31; //60;
  
struct LinearBasis
{
    ll a[MAXL + 1];
  
    LinearBasis()
    {
        std::fill(a, a + MAXL + 1, 0);
        //memset(a,0,128U);
    }
  
    bool insert(ll t)
    {
        // 逆序枚举二进制位
        for (int j = MAXL; j >= 0; j--)
        {
            // 如果 t 的第 j 位为 0，则跳过
            if (!(t & (1ll << j))) continue;
  
            // 如果 a[j] != 0，则用 a[j] 消去 t 的第 j 位上的 1
            if (a[j]) t ^= a[j];
            else
            {
                // 找到可以插入 a[j] 的位置
  
                // 用 a[0...j - 1] 消去 t 的第 [0, j) 位上的 1
                // 如果某一个 a[k] = 0 也无须担心，因为这时候第 k 位不存在于线性基中，不需要保证 t 的第 k 位为 0
                for (int k = 0; k < j; k++) if (t & (1ll << k)) t ^= a[k];
  
                // 用 t 消去 a[j + 1...L] 的第 j 位上的 1
                for (int k = j + 1; k <= MAXL; k++) if (a[k] & (1ll << j)) a[k] ^= t;
  
                // 插入到 a[j] 的位置上
                a[j] = t;
  
                // 不要忘记，结束插入过程
                return false;
            }
  
            // 此时 t 的第 j 位为 0，继续寻找其最高位上的 1
        }
        return true;
        // 如果没有插入到任何一个位置上，则表明 t 可以由 a 中若干个元素的异或和表示出，即 t 在 span(a) 中
    }
    //check if x in the span of base
    bool check(ll x){
        for(int i=MAXL;i>=0;i--){
            if(x&(1ll<<i)){
                    if(!a[i]) return 0;
                    else x^=a[i];
            }
        }
        return 1;
    }
    ll & operator [](int x){
        return a[x];
    }
};
LinearBasis tmpLB,v1;
void inter(LinearBasis &x,LinearBasis &y,LinearBasis &ans)
{
    memset(ans.a,0,sizeof(ans.a));
    tmpLB=v1=x;
    for(int i=0;i<=MAXL;i++)
    {
        if(y[i])
        {
            ll x=y[i],now=0;
            int f=0;
            for(int j=MAXL;j>=0;j--)
            {
                if(x&(1<<j))
                {
                    if(!tmpLB[j]){
                        f=1;
                        tmpLB[j]=x;
                        v1[j]=now;
                        break;
                    }
                    else{
                        x^=tmpLB[j];
                        now^=v1[j];
                    }
                }
            }
            if(!f) ans.insert(now);
        }
    }
}
 
// void inter(LinearBasis& a,LinearBasis& b,LinearBasis &res){
//     //LinearBasis res;
//     for(int i=0;i<=MAXL;++i){
//         if(a.check(b.a[i])){
//             res.insert(b.a[i]);
//         }
//     }
//     //return res;
// }
  
int n,m,sz;
ll cnt=0,tmp;
  
LinearBasis tr[maxn<<2];
  
void build(int o,int l,int r){
    if(l==r){
        scanf("%d",&sz);
        for(int i=1;i<=sz;++i){
            scanf("%lld",&tmp);
            tr[o].insert(tmp);
        }  
        return ;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    inter(tr[o<<1],tr[o<<1|1],tr[o]);
}
  
int ql,qr;
bool query(int o,int l,int r){
    if(ql<=l&&r<=qr){
        return tr[o].check(tmp);
    }
    int mid=(l+r)>>1;
    LinearBasis a,b;
    if(ql<=mid) if(!query(o<<1,l,mid)) return 0;//res=inter(res,query(o<<1,l,mid));
    if(mid<qr)  if(!query(o<<1|1,mid+1,r)) return 0;//res=inter(res,query(o<<1|1,mid+1,r));
    return 1;
}
  
int main(){
    //cout<<(sizeof(tr))/sizeof(ll)/1024<<endl;
    ll a[MAXL+1];
    //cout<<sizeof(a)<<endl;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    LinearBasis cur;
    while(m--){
        scanf("%d%d%lld",&ql,&qr,&tmp);
        //memset(cur.a,0,sizeof(cur.a));//error1
        puts(query(1,1,n)?"YES":"NO");
    }
}
/*
1 4
2 1 2
2 3 2
1 1 0
1 2 3
1 3 4
2 3 2
*/