男默女泪！线性基求交全网最通俗解释

Posted on | In ,

https://ac.nowcoder.com/acm/contest/884/B

题目大意就是对于n个集合，每个集合最多32个unsigned int，给出m个询问问对于[l,r]的集合，是否都能各自通过异或得到x。很明显要维护区间线性基的交。

这道题我第一遍做的时候对线性基的理解还不是很深……当时误认为了求出的线性基都只有一个二进制位1，所以合并的时候就直接取与，然后就wa在了百分之六十。后来突然意识到有可能线性基的低位还有1存在，但并未考虑。后来上网查线性基取交的正确做法，给出的那套线代角度的证明实在看不懂，自己想了好久……这里用大白话给出我自己的直观理解。

我们首先要知道，线性基求交的本质是对于两个集合A、B和它们的基baseA、baseB，找到一组基使得既可以通过baseA表达，也可以通过baseB表达。一个通常的想法可以是，这个基脱胎于这两组基中的一组，比如我们对baseB挨个判断是否能被baseA表达，如果可以，这个基就是共有的。这里会有一个问题就是，baseB的低位1并未被完全清除，比如11和01，其实可以产生10这个基，于是我们修改表述为：要求选出baseB中的那些可以被baseA和baseB中低位基共同表达出来的基（等式转化一下就变成了，找出baseB中i和i以下某些基的异或和，这个异或和同样能被baseA表示）。

这里大部分人给出的做法是：在用baseA不断削减baseB中的某个基的同时，如果遇到削减不下去的情况，就把当前值增添到新baseA中（代码中为all），以待后续的基使用，同时记录下来削减到这个地步所需要的baseA（代码中为d），最终，如果某个baseB中的基，能够被一些baseA（在低位baseB的帮助下）削减至0，那么这些baseA的异或值就是一个合法新基，同样用到的baseBi和它的低位“帮手”的异或值也是这个。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
using namespace std;
#define lson (o<<1)
#define rson (o<<1|1)
#define ll long long
const int maxn=5e4+2;
const int maxp=32;
int n,m;

ll read(){
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
struct base{
    ll p[maxp];
    base(){ memset(p,0,sizeof(p));}
    void clr(){
        for(int i=maxp-1;i;i--){
            if(p[i]){
                for(int j=i-1;j>=0;j--){
                    if(p[j]&&(p[i]&(1ll<<j)))
                        p[i]^=p[j];
                }
            }
        }
    }
    bool check(ll x){
        for(int i=maxp-1;i>=0;i--){
            if(x&(1ll<<i)){
                if(p[i]) x^=p[i];
                else return false;
            }
        }
        return true;
    }
}initp[maxn],tree[maxn<<2];

void inst(ll x,base& bse){
    for(int i=maxp-1;i>=0;i--){
        if(x&(1ll<<i)){
            if(!bse.p[i]){
                bse.p[i]=x;
                break;
            }else
                x^=bse.p[i];
        }
        if(x==0)
            break;
    }
}

base d,all;
base merge(const base& a,const base& b){
    base res;
    d=a,all=a; //all装的是目前所有可用的低位基
    ll k;	//k是把baseBi和它的低位帮手削减至0所用到的baseA的异或和
    for(int i=0;i<maxp;i++){
        if(b.p[i]==0) continue;
        ll v=b.p[i];k=0;
        int j;
        for(j=i;j>=0;j--){
            if(((1ll<<j)&v)){
                if(all.p[j]>0){
                    v^=all.p[j];
                    k^=d.p[j];
                }else{
                    break;
                }
            }
        }
        if(!v)
            res.p[i]=k;
        else{
            all.p[j]=v;
            d.p[j]=k;
        }
    }
    return res;
}

/*
base merge(const base& a,const base& b){
    base res;
    for(int i=0;i<maxp;i++){
        if(b.p[i]==0)
            continue;
        ll v=b.p[i];
        for(int j=i;j>=0;j--){
            if((1ll<<j)&v){
                if(a.p[j]){
                    v^=a.p[j];
                }else{
                    break;
                }
            }
        }
        if(v==0)
            res.p[i]=b.p[i];
    }
    return res;
}
*/


void build(int o,int l,int r){
    if(l==r){
        tree[o]=initp[l];
        return;
    }
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
    tree[o]=merge(tree[lson],tree[rson]);
}
bool query(int o,int l,int r,int L,int R,ll x){
    if(l>=L&&r<=R){
        return tree[o].check(x);
    }
    bool f1=true,f2=true;
    int mid=(l+r)/2;
    if(L<=mid){
        f1=query(lson,l,mid,L,R,x);
    }
    if(R>mid){
        f2=query(rson,mid+1,r,L,R,x);
    }
    return f1&&f2;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,k;i<=n;i++){
        scanf("%d",&k);ll x;
        for(int j=1;j<=k;j++){
            x=read();
            inst(x,initp[i]);
        }
        //initp[i].clr();
    }
    build(1,1,n);
    while(m--){
        int l,r;
        ll x;
        scanf("%d%d",&l,&r);x=read();
        printf(query(1,1,n,l,r,x)?"YES\n":"NO\n");
    }
}

其实我自己中间有一种想法就是，预先把所有基中能清理的低位1都清理掉，这样就不用考虑baseB的低位帮手的问题了（有了它也没用）使得merge函数极为简单（注释掉的那个），但后来想到，即使baseB都“净身”，也不排除会有必须和兄弟一起才能表示baseA的情况例如（baseB={1100,0011},baseA={1111}）。其实它们是可以共同表示1111这个数字，但在我那个算法中就漏掉了。