yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P6018 [Ynoi2010] Fusion tree

发表于 分类于

P6018 [Ynoi2010] Fusion tree

题面

题目链接

解法

以后看到题目要求的修改操作里既需要 $+1$ 又需要查询 $\oplus$ 和，这个时候就可以反向建立 $01\,trie$。

首先是如何修改和 $x$ 相邻的节点。由于给定的一棵树，所以将父亲与儿子分开考虑。对每个节点维护自身的值 $val[x]$ 以及儿子的标记 $tag[x]$ 即可。对 $x$ 相邻节点 $+v$ 就将 $val[fa_x] + v$ 并且 $tag[x] + v$；对 $x$ 本身 $+v$ 则直接让 $val[x] + v$。

之后考虑维护儿子的异或和，显然是可以用 $01\,trie$ 维护的。对于单点修改，直接删除并重新插入。对于整个 $trie$ 的 $+1$ 操作，可以反向建立 $01\,trie$，大致代码如下：

1
2
3
4
5
void addone(int u) {
    swap(ch[u][0], ch[u][1]);
    if (ch[u][0]) addone(ch[u][0], k - 1);
    pushup(u);
}

这题就结束了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
 * @file:           P6018.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P6018
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false; char ch = getchar(); double tmp = 1;
    for (; !isdigit(ch); ch = getchar()) sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar((x % 10) ^ 48);
}
bool m_be;
using ll = long long;
const int MAXN = 5e5 + 10;
const int MAXM = 2e7 + 10;
const int INF = 0x3f3f3f3f;
int n, q, a[MAXN], fa[MAXN], tag[MAXN];
int tot, rt[MAXM], siz[MAXM], sum[MAXM], ch[MAXM][2];
vector<int> g[MAXN];
void pushup(int u) {
    siz[u] = siz[ch[u][0]] ^ siz[ch[u][1]];
    sum[u] = ((sum[ch[u][0]] ^ sum[ch[u][1]]) << 1) ^ siz[ch[u][1]];
}
void insert(int u, int p, int k = 30) {
    if (k == -1) return void(siz[u] ^= 1);
    if (!ch[u][p & 1]) ch[u][p & 1] = ++tot;
    insert(ch[u][p & 1], p >> 1, k - 1), pushup(u);
}
void addone(int u, int k = 30) {
    if (k == -1) return;
    swap(ch[u][0], ch[u][1]);
    if (ch[u][0]) addone(ch[u][0], k - 1);
    pushup(u);
}
void build(int u, int f) {
    fa[u] = f, rt[u] = ++tot;
    for (auto v : g[u]) {
        if (v == f) continue;
        build(v, u), insert(rt[u], a[v]);
    }
}
inline int get(int x) { return a[x] + tag[fa[x]]; }
bool m_ed;
signed main() {
    // debug("Mem %.5lfMB.", fabs(&m_ed - &m_be) / 1024 / 1024);
    read(n), read(q);
    for (int i = 1; i < n; ++i) {
        int u, v; read(u), read(v);
        g[u].push_back(v), g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) read(a[i]);
    build(1, 0), insert(rt[0] = ++tot, a[1]);
    while (q--) {
        int op, x, v;
        read(op), read(x);
        if (op == 1) {
            addone(rt[x]), ++tag[x];
            if (int f = fa[x])
                insert(rt[fa[f]], get(f)), ++a[f], insert(rt[fa[f]], get(f));
        } else if (op == 2) {
            read(v);
            insert(rt[fa[x]], get(x)), a[x] -= v, insert(rt[fa[x]], get(x));
        } else {
            int ans = sum[rt[x]];
            if (fa[x]) ans ^= get(fa[x]);
            write(ans), putchar('\n');
        }
    }
    return 0;
}