洛谷3292 [SCOI2016]幸运数字

Luogu

BZOJ

分析

线性基+倍增+树链剖分。

首先预处理出 $lb[i][j]$ 表示 $i$ 向上 $2^j$ 个节点的权值的线性基。

查询就直接合并路径上的所有线性基,然后查一下 $\max$ 就行了。

时间复杂度大概是 $O\big((n+Q)\log^3n\big)$。

但是因为我的线性基是跟 Menci 学的,所以在 $\mathrm{BZOJ}$ 上跑不过。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=20000+10;
const int L=60;

struct LinearBasis {
    ll a[L+1];

    LinearBasis() { memset(a,0,sizeof(a)); }
    inline void clear() { memset(a,0,sizeof(a)); }
    inline void insert(ll t) {
        for (re int i=L;~i;--i) {
            if (!(t&(1ll<<i))) continue;
            if (a[i]) t^=a[i];
            else {
                for (re int j=0;j<i;++j) if (t&(1ll<<j)) t^=a[j];
                for (re int j=i+1;j<=L;++j) if (a[j]&(1ll<<i)) a[j]^=t;
                a[i]=t; return;
            }
        }
    }
    inline ll queryMax() {
        ll res=0;
        for (re int i=0;i<=L;++i) res^=a[i];
        return res;
    }
} lb[17][N];

inline LinearBasis merge(LinearBasis a,LinearBasis b) {
    LinearBasis res=a;
    for (re int i=0;i<=L;++i) res.insert(b.a[i]);
    return res;
}

int n,Q;
int lg[N];
ll val[N];

struct Edge { int v,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int fa[N],sz[N],dep[N],hson[N],top[N],dfn[N],tim=0;

inline void dfs1(int u,int f) {
    fa[u]=f,sz[u]=1,dep[u]=dep[f]+1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (!hson[u]||sz[v]>sz[hson[u]]) hson[u]=v;
    }
}

inline void dfs2(int u,int anc) {
    top[u]=anc,dfn[u]=++tim,lb[0][tim].insert(val[u]);
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=hson[u]&&e[i].v!=fa[u]) dfs2(e[i].v,e[i].v);
}

inline LinearBasis get(int l,int r) {
    int t=lg[r-l+1];
    return merge(lb[t][l],lb[t][r-(1<<t)+1]);
}

int main() {
    n=read(),Q=read();
    for (re int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (re int i=1;i<=n;++i) val[i]=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs1(1,0),dfs2(1,1);
    for (re int i=1;i<=lg[n];++i)
        for (re int j=1;j+(1<<i)-1<=n;++j)
            lb[i][j]=merge(lb[i-1][j],lb[i-1][j+(1<<i-1)]);
    while (Q--) {
        int u=read(),v=read(); LinearBasis ans;
        while (top[u]!=top[v]) {
            if (dep[top[u]]<dep[top[v]]) swap(u,v);
            ans=merge(ans,get(dfn[top[u]],dfn[u]));
            u=fa[top[u]];
        }
        if (dep[u]<dep[v]) swap(u,v);
        ans=merge(ans,get(dfn[v],dfn[u]));
        printf("%lld\n",ans.queryMax());
    }
    return 0;
}
最后修改:2019 年 09 月 26 日 12 : 59 PM

发表评论