2019年牛客多校第四场 B题xor(线段树+线性基交)

题目链接

传送门

题意

给你\(n\)个基底，求\([l,r]\)内的每个基底是否都能异或出\(x\)。

思路

线性基交板子题，但是一直没看懂咋求，先偷一份咖啡鸡板子写篇博客吧~

线性基交学习博客：传送门

代码实现如下

#include <set>

#include <map>

#include <deque>

#include <queue>

#include <stack>

#include <cmath>

#include <ctime>

#include <bitset>

#include <cstdio>

#include <string>

#include <vector>

#include <cassert>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

using namespace std;

typedef unsigned int ui;

typedef long long LL;

typedef pair<LL, LL> pLL;

typedef pair<LL, int> pLi;

typedef pair<int, LL> pil;;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define lson rt<<1

#define rson rt<<1|1

#define lowbit(x) x&(-x)

#define name2str(name) (#name)

#define bug printf("*********\n")

#define debug(x) cout<<#x"=["<<x<<"]" <<endl

#define FIN freopen("D://Code//in.txt","r",stdin)

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define  fuck(x)     cout<<#x" = "<<x<<endl

const double eps = 1e-8;

const int mod = 1000000007;

const int maxn = 50000 + 7;

const double pi = acos ( -1 );

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3fLL;

ui x, a[maxn][35];

int n, q, sz, l, r;

struct base{

    ui r[32];

    ui f[32];

    bool ins(ui x){

        for (int i=31;i>=0;i--)

            if (x>>i){

                if (!r[i]) {r[i]=x;return 1;}

                x^=r[i];

                if (!x) return 0;

            }

        return 0;

    }

    void ins2(ui x){

        ui tmp=x;

        for (int i=31;i>=0;i--)

            if (x>>i){

                if (!r[i]) {f[i]=tmp;r[i]=x;return;}

                x^=r[i]; tmp^=f[i];

                if (!x) return;

            }

        return;

    }

    bool find(ui x){

        for (int i=31;i>=0;i--)

            if (x>>i){

                if (!r[i]) return 0;

                x^=r[i];

            }

        return x==0;

    }

    ui calc(ui x){

        ui ret=0;

        for (int i=31;i>=0;i--){

            if (x>>i){

                ret^=f[i];

                x^=r[i];

            }

        }

        return ret;

    }

    void print(){

        for (int i=0;i<32;i++)cout<<r[i]<<' ';cout<<endl;

    }

    void clear(){

        for (int i=0;i<32;i++) r[i]=f[i]=0;

    }

};

struct node {

    int l, r;

    base val;

}segtree[maxn<<2];

void push_up(int rt) {

    base tmp = segtree[lson].val;

    base ans;

    ans.clear();

    for(int i = 31; i >= 0; --i) {

        ui x = segtree[rson].val.r[i];

        if(tmp.find(x)) {

            ans.ins(x^tmp.calc(x));

        } else tmp.ins2(x);

    }

    segtree[rt].val = ans;

}

void build(int rt, int l, int r) {

    segtree[rt].l = l, segtree[rt].r = r;

    if(l == r) {

        for(int i = 0; i <= 31; ++i) segtree[rt].val.ins(a[l][i]);

        return;

    }

    int mid = (l + r) >> 1;

    build(lson, l, mid);

    build(rson, mid + 1, r);

    push_up(rt);

}

bool query(int rt, int l, int r, LL x) {

    if(segtree[rt].l == l && segtree[rt].r == r) {

        return segtree[rt].val.find(x);

    }

    int mid = (segtree[rt].l + segtree[rt].r) >> 1;

    if(r <= mid) return query(lson, l, r, x);

    else if(l > mid) return query(rson, l, r, x);

    else {

        return query(lson, l, mid, x) && query(rson, mid + 1, r, x);

    }

}

int main() {

#ifndef ONLINE_JUDGE

FIN;

#endif // ONLINE_JUDGE

    scanf("%d%d", &n, &q);

    for(int i = 1; i <= n; ++i) {

        scanf("%d", &sz);

        for(int j = 0; j < sz; ++j) scanf("%lld", &a[i][j]);

        for(int j = sz; j <= 31; ++j) a[i][j] = 0;

    }

    build(1, 1, n);

    while(q--) {

        scanf("%d%d%lld", &l, &r, &x);

        if(query(1, l, r, x)) printf("YES\n");

        else printf("NO\n");

    }

    return 0;

}