洛谷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;
}