P15044 [UOI 2022 II Stage] 树 题解

· · 题解

不会线性基的看这里——《初中生都能看懂的线性基详解》，以下内容均来自我的这篇专栏。

第 k 小异或和

注意是所有线性组合去重后，即线性基元素组出的第 k 小。

对于线性基来说，其元素互相异或不改变其表示的线性空间。对于存在 a_i 的二进制位，我们不妨将其消成第 i 位只有 a_i 为 1，如此这些位都是独立的。

时间复杂度为 O(\log^2V)。

ll cnt,tmp[logV];
void pre(){
    cnt=0;
    for(int i=0;i<logV;++i){
        for(int j=i-1;j>=0;--j)if(a[i]&(1ll<<j))a[i]^=a[j];
        if(a[i])tmp[++cnt]=a[i];
    }
}

依旧先判断是否存在 0。然后从高到低扫过每个有值的 a_i。根据前面的内容，我们可知如果异或上它，结果的排名就在前一半，否则就在后一半。于是我们就能求第 k 小了。

要先运行 \operatorname{pre}() 函数，单个 \operatorname{kth}(k) 的时间复杂度 O(\log V)。

ll kth(ll k){
    --k;
    if(!k)return 0;
    if(k>=(1ll<<cnt))return-1;
    ll r=0;
    for(int i=0;i<cnt;++i)if(k&(1ll<<i))r^=tmp[i];
    return r;
}

线性基求并

我们知道线性基本质是一个大小为 \log V 的数组，并且可以在 O(\log^2V) 时间复杂度内进行合并。

假设现在有两个线性空间 V_1 和 V_2，线性基分别为 B_1 和 B_2，求并集 V_0=V_1\cup V_2 的线性基 B_0。

很简单，直接将 B_2 中的数全部插入到 B_1 中即可得到 B_0，建议使用结构体封装。

需要插入 O(\log V) 个数，单次插入时间复杂度为 O(\log V)，故总复杂度为 O(\log^2V)。

Linear_Basis merge(Linear_Basis B1,Linear_Basis B2){
    Linear_Basis B0=B1;
    for(int i=0;i<logV;++i)if(B2.a[i])B0.insert(B2.a[i]);
    return B0;
}

本题需要子树的线性基并动态修改。

所以树剖，采用线段树维护每个节点子树的线性基。

时间复杂度 O((n+q)\log n\log^2V)。

::::success[code]

#define N 100010
#define logV 33
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((seg[x].l+seg[x].r)>>1)
#define ll long long

struct Linear_Basis{
    ll a[logV];
    void insert(ll x){
        for(int i=logV-1;i>=0;--i){
            if(!(x&(1ll<<i)))continue;
            if(a[i])x^=a[i];
            else{a[i]=x;return;}
        }
    }
    ll cnt,tmp[logV];
    void pre(){
        cnt=0;
        for(int i=0;i<logV;++i){
            for(int j=i-1;j>=0;--j)if(a[i]&(1ll<<j))a[i]^=a[j];
            if(a[i])tmp[cnt++]=a[i];
        }
    }
    ll kth(ll k){
        --k;
        if(!k)return 0;
        if(k>=(1ll<<cnt))return-1;
        ll r=0;
        for(int i=0;i<cnt;++i)if(k&(1ll<<i))r^=tmp[i];
        return r;
    }
};

Linear_Basis merge(Linear_Basis B1,Linear_Basis B2){
    Linear_Basis B0=B1;
    for(int i=0;i<logV;++i)if(B2.a[i])B0.insert(B2.a[i]);
    return B0;
}

int n,g,q,cnt;
int dfn[N],rk[N],top[N],son[N],sz[N],fa[N];
ll a[N];
vector<int>e[N];
void dfs(int u,int f){
    fa[u]=f;
    dfn[u]=++cnt;
    rk[cnt]=u;
    sz[u]=1;
    for(int i=0;i<e[u].size();++i){
        int v=e[u][i];
        if(v==f)continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v])son[u]=v;
    }
}
void dfs2(int u,int tp){
    top[u]=tp;
    if(son[u])dfs2(son[u],tp);
    for(int i=0;i<e[u].size();++i){
        int v=e[u][i];
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}

struct node{
    Linear_Basis b;
    int l,r;
}seg[N*4];

void pushup(int x){ seg[x].b=merge(seg[ls].b,seg[rs].b); }

void build(int x,int l,int r){
    seg[x].l=l,seg[x].r=r;
    if(l==r)seg[x].b.insert(a[rk[l]]);
    else{
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(x);
    }
}

Linear_Basis query(int x,int ql,int qr){
    if(ql<=seg[x].l&&seg[x].r<=qr)return seg[x].b;
    if(qr<=mid)return query(ls,ql,qr);
    if(ql>mid)return query(rs,ql,qr);
    return merge(query(ls,ql,qr),query(rs,ql,qr));
}

void modify(int x,int p,ll v){
    if(seg[x].l==p&&seg[x].r==p){
        for(int i=logV-1;i>=0;--i)seg[x].b.a[i]=0;
        seg[x].b.insert(v);
    }
    else{
        if(p<=mid)modify(ls,p,v);
        else modify(rs,p,v);
        pushup(x);
    }
}

int main(){
    n=in(),g=in();
    for(int i=1;i<n;++i){
        int u=in(),v=in();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    dfs2(1,1);
    for(int i=1;i<=n;++i)a[i]=in();
    build(1,1,n);
    q=in();
    while(q--){
        int o=in();
        if(o==1){
            int p=in();ll v=in();
            modify(1,dfn[p],v);
        }
        else{
            int u=in();ll k=in();
            Linear_Basis res=query(1,dfn[u],dfn[u]+sz[u]-1);
            res.pre();
            printf("%lld\n",res.kth(k));
        }
    }
    I love segment_tree
}

::::