P6018 [Ynoi2010] Fusion tree 题解

标签：curr fa int 题解 Ynoi2010 P6018 const 节点 define

题目链接：Fusion tree

大部分人貌似用的边权 01 Trie，实际这题用点权 01 Trie 类似文艺平衡树去写更方便。

考虑两种常见的区间维护：

线段树。使用的是父节点信息是归并了左右区间的信息，适用于不需要考虑父节点的贡献的信息。
文艺平衡树。每个点就是一个信息，归并左右子树，外加当前自身节点的信息归并。

0-1Trie 在平衡树板题当中倒是有很多人拿来去代替。这里讲讲本题怎么用第二种方式去写。

0-1 Trie 最基本的信息：当前所在一层为某一位，即某个节点最基本的信息为某一位的信息，然后这一位可以拆成 "0/1"，同时这一位是 \(0\) 或者是 \(1\) 的信息。

对于树类维护信息思考：从单点基本信息 \(\Rightarrow\) 归并后的信息。

思考本题大致需要维护什么信息？

基本的每一位的 \(0\) 或者 \(1\) 的数量，再考虑本题询问异或和，那显然我们需要知道整棵树所存的树的异或和，这东西就是我们需要 "归并" 得到的。考虑如何由左右子树 \(+\) 当前这一位去归并得到。

异或和和加法这一类问题是差不多的，可加可减。

考虑：

\(1\rightarrow 1\times 10+2 \rightarrow 12 \times 10 +3 \rightarrow 123\times 10 +4 \rightarrow 1234\)

加法其实可以这么去累计每一位的贡献。那么我们来考虑异或和是否也能这样得到。

对于一个数而言：

\( 1<<1 \oplus 2 \rightarrow 12<<1 \oplus 3 \rightarrow 123<<1 \oplus 4 \rightarrow 1234 \)

一样是从高位到低位，我们树类结构显然是从叶子往上归并，那么这个 0-1 Trie 显然应该由低位到高位的去建，让叶子节点为高位信息，这样才能类似上述过程父节点归并信息。这和常用的 0-1 Trie 略带区别。

现在不是一个数了，而是若干个数，还是考虑相邻两位的合并：

已经知道左右子树的异或和，显然它们的异或结果即为高位异或和，按上述描述需要右移一位。
还知道当前这一位的数量，要合并信息，则需要考虑当前这一位是否有贡献，那么我们从最开始的定义来看。首先它一定要属于 \(1\) 的贡献，因为对于每一位来说都有对应的一层表示，对应的一层则有两个树节点，一个表示是 \(0\)，一个表示是 \(1\) 的贡献。那么是 \(0\) 的数这一位异或结果无论如何都是 \(0\)。考虑如果是 \(1\) 的数则需要考虑数量，如果是奇数则有贡献，否则偶数个 \(1\) 异或结果是 \(0\)。

到此，你会发现还需要维护一个信息：\(type\)，表示当前节点的类型，是 \(0\) 还是 \(1\)，和析合树的析点与合点类型定义方式一致。这样一来，这个归并信息代码就出来了：

参照代码

xorSum(curr) = (xorSum(left(curr)) ^ xorSum(right(curr))) << 1 ^ cnt(curr) & type(curr) & 1;

把左右子树异或和移动一位，当前位则为低一位，他是否贡献，由数量和类型共同决定。

现在难点来了，对于 0-1 Trie 来说，是具有空根节点的概念的，即根节点并不表示任何一位，而是归并左右节点信息，这玩意不就和线段树一样吗？所有需要特判。

回到本题

考虑本题怎么做。观察到它的问法很特别，维护一个点的 \(1\) 邻域的若干个点。无根树不好做，我们变为有根树，就确定 \(1\) 为根。考虑每个点的邻域的点，分为儿子和一个父亲，考虑 0-1 Trie去维护，考虑如果父亲加入这个树，那么当父亲改变时，实际上会影响下方包含它的树，与上方包含它的树，那么考虑到这玩意是单点维护，那么这个点的改变就不会影响它的所有儿子的树了，否则它改变时，下方包含的 Trie 树全都得改变，难以接受，所以父亲单独维护时，只需要考虑上方包含它的 Trie树，显然就一个。

看图就能理解我说的意思，所以 \(fa\) 单独维护，它的变化就只会影响 \(fa[fa]\) 的树。

考虑第一个操作，全局 \(+1\)，先考虑 0-1 Trie 咋做这玩意？

搬一张 oiwike 的图看看，其实很简单，从低位到高位找到第一个 \(0\)，然后设做 \(1\)，它低位的 \(1\) 则变成 \(0\) 即可。但这是一个数的，若干个数同时做，其实不就是类似 \(0-1\) 线段树内的所有 \(0 \rightarrow 1\) 操作吗？而所有的 \(1\) 则变成 \(0\)，所以本质就是对偶问题的交换答案，只需要交换两棵树即可。如何再暴力修改父亲的父亲树，删除父亲节点的值，然后 \(+1\) 后再插入回去。

注意交换细节，交换后 \(type\) 需要注意重新赋值了，所以导致原来的信息需要重新 pushUp，注意到这一点就没问题了。

操作三就是查找，先不考虑操作二，操作三查找显然是邻域查找异或上父亲的值就行了。现在考虑操作一对操作三的影响，显然那个邻域儿子异或值没啥影响，主要是父亲的贡献，我们发现操作一会使得对所有的 \(son\) 都有 \(+1\) 操作，这个 \(+1\) 显然不能暴力，那么就类似标记永久化，打 lazy，\(lazy[curr]\) 表示 \(curr\) 的所有节点 \(+\) 多少。这样一来就能很快拿到一个点的准确值为：\(val[curr]+lazy[fa[curr]]\)。

这样一来一三操作解决了。二操作就是一棵 \(0-1 Trie\) 上删除原来的这个数，再加上新的这个数，考虑一下影响只有它父亲的 0-1 Trie 树。至此，都解决了。

参照代码

#include <bits/stdc++.h>

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#define isPbdsFile

#ifdef isPbdsFile

#include <bits/extc++.h>

#else

#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>

#endif

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

template <typename T>
int disc(T* a, int n)
{
    return unique(a + 1, a + n + 1) - (a + 1);
}

template <typename T>
T lowBit(T x)
{
    return x & -x;
}

template <typename T>
T Rand(T l, T r)
{
    static mt19937 Rand(time(nullptr));
    uniform_int_distribution<T> dis(l, r);
    return dis(Rand);
}

template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
    return (a % b + b) % b;
}

template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
    a %= c;
    T1 ans = 1;
    for (; b; b >>= 1, (a *= a) %= c) if (b & 1) (ans *= a) %= c;
    return modt(ans, c);
}

template <typename T>
void read(T& x)
{
    x = 0;
    T sign = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-') sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    x *= sign;
}

template <typename T, typename... U>
void read(T& x, U&... y)
{
    read(x);
    read(y...);
}

template <typename T>
void write(T x)
{
    if (typeid(x) == typeid(char)) return;
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 ^ 48);
}

template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
    write(x), putchar(c);
    write(c, y...);
}


template <typename T11, typename T22, typename T33>
struct T3
{
    T11 one;
    T22 tow;
    T33 three;

    bool operator<(const T3 other) const
    {
        if (one == other.one)
        {
            if (tow == other.tow) return three < other.three;
            return tow < other.tow;
        }
        return one < other.one;
    }

    T3()
    {
        one = tow = three = 0;
    }

    T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
    {
    }
};

template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
    if (x < y) x = y;
}

template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
    if (x > y) x = y;
}

constexpr int N = 5e5 + 10;
constexpr int T = 20; //最高位
int n, m;
int a[N], fa[N], lazy[N];
vector<int> child[N];

struct Trie
{
    int xorSum;
    int cnt;
    int child[2];
    int type; //类型 0/1
} node[N * T];

#define xorSum(x) node[x].xorSum
#define cnt(x) node[x].cnt
#define type(x) node[x].type
#define child(x,y) node[x].child[y]
#define left(x) child(x,0)
#define right(x) child(x,1)
int root[N], cnt;

//归并信息,idx=0则为根节点,不表示任何一位
inline void pushUp(const int curr, const int idx)
{
    const int v = idx != 0; //是否是根节点,非根节点则为 ans<<1^(当前点的贡献)
    xorSum(curr) = (xorSum(left(curr)) ^ xorSum(right(curr))) << v ^ v & type(curr) & cnt(curr);
}

inline void update(int& curr, const int val, const int diff, const int type = 0, const int idx = 0)
{
    if (idx > T) return;
    if (!curr) curr = ++cnt;
    type(curr) = type;
    cnt(curr) += diff;
    update(child(curr, val&1), val >> 1, diff, val & 1, idx + 1);
    pushUp(curr, idx);
}

//全局+1
inline void addOne(const int curr, const int idx = 0)
{
    swap(left(curr),right(curr));
    type(left(curr)) = 0, type(right(curr)) = 1; //注意重新赋值类型
    if (left(curr)) addOne(left(curr), idx + 1);
    //注意左右子树的答案需要重新计算,因为类型变了
    pushUp(left(curr), idx + 1);
    pushUp(right(curr), idx + 1);
    pushUp(curr, idx);
}

//真实值
inline int getVal(const int curr)
{
    return a[curr] + lazy[fa[curr]];
}

//操作一
inline void op1(const int curr)
{
    addOne(root[curr]); //儿子全局+1
    const int old = getVal(fa[curr]);
    //父亲的影响
    if (fa[fa[curr]])
    {
        update(root[fa[fa[curr]]], old, -1);
        update(root[fa[fa[curr]]], old + 1, 1);
    }
    if (fa[curr]) a[fa[curr]]++;
    lazy[curr]++;
}

//操作二,暴力删除,暴力添加
inline void op2(const int curr, const int val)
{
    if (fa[curr]) update(root[fa[curr]], getVal(curr), -1);
    a[curr] -= val;
    if (fa[curr]) update(root[fa[curr]], getVal(curr), 1);
}

//操作三,注意下如果只有一个点,没有邻域返回0
inline int op3(const int curr)
{
    return xorSum(root[curr]) ^ getVal(fa[curr]);
}

//为所有儿子节点建树
inline void dfs(const int curr, const int pa)
{
    fa[curr] = pa;
    for (const int nxt : child[curr])
    {
        if (nxt == pa) continue;
        update(root[curr], a[nxt], 1);
        dfs(nxt, curr);
    }
}


inline void solve()
{
    cin >> n >> m;
    forn(i, 1, n-1)
    {
        int u, v;
        cin >> u >> v;
        child[u].push_back(v);
        child[v].push_back(u);
    }
    forn(i, 1, n) cin >> a[i];
    dfs(1, 0);
    while (m--)
    {
        int op, curr, val;
        cin >> op >> curr;
        if (op == 1) op1(curr);
        else if (op == 2) cin >> val, op2(curr, val);
        else cout << op3(curr) << endl;
    }
}

signed int main()
{
    // MyFile
    Spider
    //------------------------------------------------------
    // clock_t start = clock();
    int test = 1;
    //    read(test);
    // cin >> test;
    forn(i, 1, test) solve();
    //    while (cin >> n, n)solve();
    //    while (cin >> test)solve();
    // clock_t end = clock();
    // cerr << "time = " << double(end - start) / CLOCKS_PER_SEC << "s" << endl;
}

\(op1/op2\) 单次操作 \(O(\log{V})\)。\(op3\) 则是 \(O(1)\)

\[最坏时间复杂度为:\ O((n+m)\log{V}) \]

标签：curr,fa,int,题解,Ynoi2010,P6018,const,节点,define
From： https://www.cnblogs.com/Athanasy/p/18145803

P6018 [Ynoi2010] Fusion tree 题解

题目链接：Fusion tree

回到本题

相关文章

赞助商

阅读排行