BZOJ 4568 [Scoi2016]幸运数字

题目链接https://www.lydsy.com/JudgeOnline/problem.php?id=4568

题意:略。

思路:两种做法,一种做法是树链剖分转成线性序列后用线段树维护区间线性基,还有一种做法是LCA倍增的时候让线性基也同时倍增,查询的时候跟着LCA往上跳同时暴力合并线性基即可,不会算复杂度,感觉两者的log数是一样多的,但实测确实是后者快很多,还有一种做法是点分治,还不会,留坑以后补。

树链剖分+线段树+线性基

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=20000+10;
const int L=60;
struct LinearBasis{
    ll a[L+1];
    LinearBasis(){
        fill(a,a+L+1,0);
    }
    void insert(ll t){
        for (int j=L;j>=0;j--){
            if (!t) return;
            if (!(t&(1LL<<j))) continue;
            /*if (a[j]) t^=a[j];
            else{
                for (int k=0;k<j;k++) if (t&(1LL<<k)) t^=a[k];
                for (int k=j+1;k<=L;k++) if (a[k]&(1LL<<j)) a[k]^=t;
                a[j]=t;
                return;
            }*/
            if (a[j]) t^=a[j];
            else{
                a[j]=t;
                return;
            }
        }
    }
    void merge(const LinearBasis& rhs){
        for (int i=0;i<=L;i++) insert(rhs.a[i]);
    }
    ll querymax(){
        ll ret=0;
        // for (int i=0;i<=L;i++) ret^=a[i];
        for (int i=L;i>=0;i--){
            if ((ret^a[i])>ret) ret^=a[i];
        }
        return ret;
    }
}p[N<<2];
int n,q,x,y,i,dfs_clock,son[N],fa[N],sz[N],dep[N],bel[N],id[N],rk[N];
ll val[N];
vector<int>G[N];
LinearBasis merge(const LinearBasis&a,const LinearBasis&b){
    LinearBasis res=a;
    for (int i=0;i<=L;i++) res.insert(b.a[i]);
    return res;
}
void dfs(int u,int f){
    dep[u]=(f?dep[f]+1:0),son[u]=-1,sz[u]=1,fa[u]=f;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if (son[u]==-1 || sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int f){
    bel[u]=f;
    id[u]=++dfs_clock;
    rk[id[u]]=u;
    if (son[u]==-1) return;
    dfs2(son[u],f);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
void pushup(int root){p[root]=merge(p[root<<1],p[root<<1|1]);}
void build(int root,int l,int r){
    if (l==r){
        p[root].insert(val[rk[l]]);
        return;
    }
    int mid=l+((r-l)>>1);
    build(lson);
    build(rson);
    pushup(root);
}
LinearBasis query(int root,int l,int r,int L,int R){
    if (L<=l&&r<=R) return p[root];
    int mid=l+((r-l)>>1);
    if (R<=mid) return query(lson,L,R);
    else if (mid<L) return query(rson,L,R);
    else return merge(query(lson,L,R),query(rson,L,R));
} 
LinearBasis work(int u,int v){
    LinearBasis res;
    while (bel[u]!=bel[v]){
        if (dep[bel[u]]<dep[bel[v]]) swap(u,v);
        res.merge(query(1,1,n,id[bel[u]],id[u]));
        u=fa[bel[u]];
    }
    if (id[u]>id[v]) swap(u,v);
    res.merge(query(1,1,n,id[u],id[v]));
    return res;
}
int main(){
    read(n),read(q);
    for (i=1;i<=n;i++) read(val[i]);
    for (i=1;i<n;i++){
        read(x),read(y);
        G[x].PB(y);
        G[y].PB(x);
    }
    dfs(1,0);
    dfs2(1,1);
    build(1,1,n);
    for (i=1;i<=q;i++){
        read(x),read(y);
        printf("%lld\n",work(x,y).querymax());
    }
    return 0;
}

LCA+倍增+线性基

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=20000+10;
const int L=60;
struct LinearBasis{
    ll a[L+1];
    LinearBasis(){
        fill(a,a+L+1,0);
    }
    void insert(ll t){
        for (int j=L;j>=0;j--){
            if (!t) return;
            if (!(t&(1LL<<j))) continue;
            if (a[j]) t^=a[j];
            else{
                a[j]=t;
                return;
            }
        }
    }
    void merge(const LinearBasis& rhs){
        for (int i=0;i<=L;i++) insert(rhs.a[i]);
    }
    ll querymax(){
        ll ret=0;
        for (int i=L;i>=0;i--){
            if ((ret^a[i])>ret) ret^=a[i];
        }
        return ret;
    }
}p[N][16];
int n,q,x,y,i,dfs_clock,parent[N][16],dep[N];
ll val[N];
vector<int>G[N];
LinearBasis merge(const LinearBasis&a,const LinearBasis&b){
    LinearBasis ret=a;
    for (int i=0;i<=L;i++) ret.insert(b.a[i]);
    return ret;
}
void dfs(int u,int f){
    dep[u]=(f?dep[f]+1:0);
    parent[u][0]=f;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
    }
}
void init(){
    for (int k=0;k<15;k++){
        for (int v=1;v<=n;v++){
            if (parent[v][k]<0) continue;
            parent[v][k+1]=parent[parent[v][k]][k];
            p[v][k+1]=merge(p[v][k],p[parent[v][k]][k]);
        }
    }
}
ll work(int u,int v){
    LinearBasis ret;
    if (dep[u]>dep[v]) swap(u,v);
    for (int k=15;k>=0;k--){
        if (((dep[v]-dep[u])>>k)&1){
            ret.merge(p[v][k]);
            v=parent[v][k];
        }
    }
    if (u!=v){
        for (int k=15;k>=0;k--){
            if (parent[u][k]!=parent[v][k]){
                ret.merge(p[u][k]);
                ret.merge(p[v][k]);
                u=parent[u][k];
                v=parent[v][k];
            }
        }
        ret.insert(val[u]);
        ret.insert(val[v]);
        u=parent[u][0];
    }
    ret.insert(val[u]);
    return ret.querymax();
}
int main(){
    memset(parent,-1,sizeof(parent));
    read(n),read(q);
    for (i=1;i<=n;i++) read(val[i]),p[i][0].insert(val[i]);
    for (i=1;i<n;i++){
        read(x),read(y);
        G[x].PB(y);
        G[y].PB(x);
    }
    dfs(1,0);
    init();
    for (i=1;i<=q;i++){
        read(x),read(y);
        printf("%lld\n",work(x,y));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注