洛谷P4592 [TJOI2018]异或(可持久化01Trie)

题意

题目链接

可持久化01trie板子题

对于两个操作分别开就行了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10, ss = maxn * 42 + 10;
const int b = 31;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, q, a[maxn], siz[maxn], son[maxn], top[maxn], fa[maxn], dep[maxn], dfn[maxn], cnt, rev[maxn];
vector<int> v[maxn];
struct trie {
    int ch[ss][2], siz[ss], tot, root[ss];
    void insert(int &k, int pre, int v) {
        k = ++tot; int now = k;
        for(int i = b; ~i; i--) {
            int nxt = v >> i & 1;
            ch[now][nxt ^ 1] = ch[pre][nxt ^ 1];
            now = ch[now][nxt] = ++tot; pre = ch[pre][nxt];
            siz[now] = siz[pre] + 1;
        }
    }
    int query1(int pre, int now, int v) {
        int ans = 0;
        for(int i = b; ~i; i--) {
            int nxt = v >> i & 1;
            if(siz[ch[now][nxt ^ 1]] - siz[ch[pre][nxt ^ 1]]) ans += (1 << i), now = ch[now][nxt ^ 1], pre = ch[pre][nxt ^ 1];
            else now = ch[now][nxt], pre = ch[pre][nxt];
        }
        return ans;
    }
    int query2(int x, int y, int lca, int fafa, int v) {
        int ans = 0;
        for(int i = b; ~i; i--) {
            int nxt = v >> i & 1;
            if(siz[ch[x][nxt ^ 1]] + siz[ch[y][nxt ^ 1]] - siz[ch[lca][nxt ^ 1]] - siz[ch[fafa][nxt ^ 1]]) 
                ans += (1 << i), x = ch[x][nxt ^ 1], y = ch[y][nxt ^ 1], lca = ch[lca][nxt ^ 1], fafa = ch[fafa][nxt ^ 1];
            else x = ch[x][nxt], y = ch[y][nxt], lca = ch[lca][nxt], fafa = ch[fafa][nxt];
        }
        return ans;
    }
} t[2];
void dfs1(int x, int _fa) {
    siz[x] = 1; t[1].insert(t[1].root[x], t[1].root[_fa], a[x]); dep[x] = dep[_fa] + 1;
    dfn[x] = ++cnt; rev[cnt] = x; fa[x] = _fa;
    for(auto &to : v[x]) {
        if(to == _fa) continue;
        dfs1(to, x);
        siz[x] += siz[to];
        if(siz[to] > siz[son[x]]) son[x] = to;
    }
}
void dfs2(int x, int topf) {
    top[x] = topf;
    if(!son[x]) return ;
    dfs2(son[x], topf);
    for(auto &to : v[x]) {
        if(top[to]) continue;
        dfs2(to, to);
    }
}
int lca(int x, int y) {
    while(top[x] ^ top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
signed main() {
    n = read(); q = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= n - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for(int i = 1; i <= n; i++) 
        t[0].insert(t[0].root[i], t[0].root[i - 1], a[rev[i]]);
    while(q--) {
        int opt = read(), x = read(), y = read(), z;
        if(opt == 1) cout << t[0].query1(t[0].root[dfn[x] - 1], t[0].root[dfn[x] + siz[x] - 1], y) << '\n';
        else {
            int lca = lca(x, y);
            z = read(), cout << t[1].query2(t[1].root[x], t[1].root[y], t[1].root[lca], t[1].root[fa[lca]], z) << '\n';
        }
    }
    return 0;
}