牛客多校第三次B——线段树维护线性基交

柔情只为你懂 2023-10-11 09:11 22阅读 0赞

写线性基交函数时调试了半天。。

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define maxn 100005
    int n,m;
    struct LB{
        ll b[35];
        int check(ll x){
            for(int i=32;i>=0;i--)if(x>>i & 1){
                if(!b[i])return 0;
                x^=b[i];
            }
            return 1;
        }
        void insert(ll x){
            for(int i=32;i>=0;i--)if(x>>i & 1){
                if(!b[i]){
                    b[i]=x;return;
                }
                x^=b[i];
            }
        }
    }base[maxn];
    void merge(LB A,LB B,LB & W){
        LB ALL,D;//W是AB的交，D[i]表示凑出bi用了哪些A的基，即每个bi对应的T 
        for(int i=0;i<=32;i++)ALL.b[i]=D.b[i]=A.b[i];
        for(int i=0;i<=32;i++)if(B.b[i]){
            ll bi=B.b[i],T=0,flag=0;
            for(int j=32;j>=0;j--)if(bi>>j & 1){
                if(!ALL.b[j]){
                    ALL.b[j]=bi;D.b[j]=T; 
                    flag=1;break;
                }
                bi^=ALL.b[j];T^=D.b[j]; 
            }
            if(!flag)
                W.insert(T);
        }
    }
    
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    LB seg[maxn<<2];
    void build(int l,int r,int rt){
        if(l==r){seg[rt]=base[l];return;}
        int m=l+r>>1;
        build(lson);build(rson);
        merge(seg[rt<<1],seg[rt<<1|1],seg[rt]);
    }
    int query(int L,int R,ll x,int l,int r,int rt){
        if(L<=l && R>=r)return seg[rt].check(x);
        int m=l+r>>1,res=1;
        if(L<=m)res&=query(L,R,x,lson);
        if(R>m)res&=query(L,R,x,rson);
        return res;
    }
    
    int main(){
        scanf("%d%d",&n,&m);
            
            for(int i=1;i<=n;i++){
                int k;scanf("%d",&k);
                while(k--){
                    ll x;scanf("%lld",&x);
                    if(!base[i].check(x))            
                        base[i].insert(x);
                }
            }
            build(1,n,1);
                    
            int l,r;ll x;
            while(m--){
                scanf("%d%d%lld",&l,&r,&x);
                if(query(l,r,x,1,n,1))puts("YES");
                else puts("NO");
            }     
    }

转载于:https://www.cnblogs.com/zsben991126/p/11269207.html