B-xor

发表于 | 分类于

problem

题意

给出n个数组(每组数个数不定)，m个询问 l, r, x
序号在区间$[l,r]$的每个数组是否都可以取出任意个数异或出x

题解

判断一个数组能否异或出x，是简单的线性基问题
判断多个线性基能否异或出x只需求出这些线性基的交，在交线性基上判断能否异或出x，多个线性基的交一定能被每个线性基分别表示，利用线段树维护区间线性基交就行，线性基求交模板是牛客上扒的咖啡鸡的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
 
using namespace std;
const int mx = 50000+10;
typedef unsigned int ui;
 
ui a[mx][35];
 
struct node{
    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<3;i++)cout<<r[i]<<' ';cout<<endl;
    }
    void clear(){
        for (int i=0;i<32;i++) r[i]=f[i]=0;
    }
}tree[mx<<2];
 
node merge(node u,node v){
    node ret,tmp;
    ret.clear(); tmp=u;
    for (int i=31;i>=0;i--) {
        ui x=v.r[i];
        if (tmp.find(x)){
            ret.ins(x^tmp.calc(x));
        } else tmp.ins2(x);
    }
    return ret;
}
 
void pushUp(int rt) {
    tree[rt] = merge(tree[rt<<1], tree[rt<<1|1]);
}
 
void build(int l, int r, int rt) {
    if (l == r) {
        for (int i = 1; i <= 32; i++)
            tree[rt].ins(a[r][i]);
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
    pushUp(rt);
}
 
bool query(int L, int R, ui x, int l, int r, int rt) {
    if (L <= l && r <= R) {
        return tree[rt].find(x);
    }
    int mid = (l + r) / 2;
    bool f1 = true, f2 = true;
    if (L <= mid) f1 = query(L, R, x, l, mid, rt<<1);
    if (mid < R) f2 = query(L, R, x, mid+1, r, rt<<1|1);
    return f1&&f2;
}
 
int main() {
    int n, m, sz;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &sz);
        for (int j = 1; j <= sz; j++)
            scanf("%u", &a[i][j]);
    }
    build(1, n, 1);
    while (m--) {
        ui l, r, x;
        scanf("%u%u%u", &l, &r, &x);
        puts(query(l, r, x, 1, n, 1) ? "YES" : "NO");
    }
    return 0;
}