Luogu 3292 [SCOI2016]幸运数字

BZOJ 4568。

感觉很板。

前置技能：线性基。放一篇感觉讲的比较丰富的博客：戳这里。

首先要求在一个序列中任意选点使得异或和最大，当然是想到线性基了。

把问题转换到树上，如果每次询问的序列是两点之间的路径，也就是说我们只要提取出树上一条路径的线性基就可以了吧。

发现线性基满足可以快速合并这个性质，如果要合并的话只要把一个暴力插到另一个里面去就行了，这样是两个$log$，我们还可以启发式合并，把小的插到大的里面去，这样会更快。

所以我们发现可以链剖或者倍增来维护这个东西，我这么懒，当然是倍增了。

注意倍增的时候是点形成的集合而不是边形成的集合。

再提两句：

　　1、线性基并不满足区间可减性，所以大力可持久化应该是不行的。

　　2、点分治可以减少一个$log$，再用$tarjan$求一求$lca$会更快。

时间复杂度$O(nlog^3n)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = ;

const int B = ;

const int Lg = ;

int n, qn, tot = , head[N], dep[N], fa[N][Lg];

ll a[N];

struct Edge {

    int to, nxt;

} e[N << ];

inline void add(int from, int to) {

    e[++tot].to = to;

    e[tot].nxt = head[from];

    head[from] = tot;

}

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

struct Lp {

    ll p[B]; int cnt;

    inline void init() {

        cnt = ;

        memset(p, 0LL, sizeof(p));

    }

    inline void ins(ll val) {

        for(int i = ; i >= ; i--) {

            if((val >> i) & ) {

                if(!p[i]) {

                    p[i] = val;

                    ++cnt;

                    break;

                }

                val ^= p[i];

            }

        }

    }

    inline ll getMax() {

        ll res = 0LL;

        for(int i = ; i >= ; i--)

            if((res ^ p[i]) > res) res ^= p[i];

        return res;

    }

} s[N][Lg];

inline Lp merge(Lp u, Lp v) {

    Lp res; res.init();

    if(u.cnt > v.cnt) {

        res = u;

        for(int i = ; i >= ; i--) {

            if(!v.p[i]) continue;

            res.ins(v.p[i]);

        }

    } else {

        res = v;

        for(int i = ; i >= ; i--) {

            if(!u.p[i]) continue;

            res.ins(u.p[i]);

        }

    }

    return res;

}

inline void swap(int &x, int &y) {

    int t = x; x = y; y = t;

}

void dfs(int x, int fat, int depth) {

    fa[x][] = fat, dep[x] = depth;

    s[x][].init();

    if(fat) s[x][].ins(a[fat]);

    for(int i = ; i <= ; i++) {

        fa[x][i] = fa[fa[x][i - ]][i - ];

        s[x][i] = merge(s[x][i - ], s[fa[x][i - ]][i - ]);

    }

    for(int i = head[x]; i; i = e[i].nxt) {

        int y = e[i].to;

        if(y == fat) continue;

        dfs(y, x, depth + );

    }

}

inline Lp getLp(int x, int y) {

    Lp res; res.init();

    res.ins(a[x]), res.ins(a[y]);

    if(dep[x] < dep[y]) swap(x, y);

    for(int i = ; i >= ; i--)

        if(dep[fa[x][i]] >= dep[y]) {

            res = merge(res, s[x][i]);

            x = fa[x][i];

        }

    if(x == y) return res;

    for(int i = ; i >= ; i--)

        if(fa[x][i] != fa[y][i]) {

            res = merge(res, s[x][i]), res = merge(res, s[y][i]);

            x = fa[x][i], y = fa[y][i];

        }

    res = merge(res, s[x][]), res = merge(res, s[y][]);

    return res;

}

inline void solve(int x, int y) {

    Lp res = getLp(x, y);

    printf("%lld\n", res.getMax());

}

int main() {

    read(n), read(qn);

    for(int i = ; i <= n; i++) read(a[i]);

    for(int x, y, i = ; i < n; i++) {

        read(x), read(y);

        add(x, y), add(y, x);

    }

    dfs(, , );

    for(int x, y; qn--; ) {

        read(x), read(y);

        solve(x, y);

    }

    return ;

}

唔，Linear Basis居然被我写成了Lp……无话可说

巴特西

Luogu 3292 [SCOI2016]幸运数字

最新文章

热门文章