P6018 [Ynoi2010] Fusion tree

题目背景和题意无关，可以跳过 ## 1.前言： Fusion Tree，中文译作融合树，是一种亚log的数据结构，与1993年由Michael L.Fredman和Dan E.Willard提出。 用途：$O( \log n/ \log w+ \log w )$时间复杂度支持插入，删除，前驱，后继，min，max，以及用于整数排序。 信息论断言对$n$个数的排序在最坏情况下需要$n\log n$次比较，不过对这个界我们还需要一些研究。 有人证明了任意unit cost RAM算法，其中只包含加法，减法，乘法，和0比较（但是不包含除法和位运算）最坏情况下需要$\Omega(n\log n)$的时间去对$n$个数排序。 如果允许使用除法和位运算，他们有一个线性时间复杂度的算法，但是这个算法对unit cost滥用。 这里我们规定我们使用的计算模型的字长是w，每个输入的数都是在$[0,2^w-1]$中的整数。 ## 2.一些记号： 对于一个集合$S$和一个整数$x$，定义$rank(S,x)$为S集合中$\le x$的元素个数。 对于一些非负整数$a$，定义$bin(a_1,...,a_n)=2^{a_i}+...+2^{a_n}$。 对于两个非负整数$a,b$，定义$msb(u,v)$为$u$和$v$最高的不相同的位。 ## 3.概述： Fusion Tree大概可以看做是一棵特殊的B-Tree，特性： 1. 叉数$B=O(w^{1/5})$ 2. 在一次搜索时，每个在搜索路径上的节点的正确的儿子可以被$O(1)$确定 从这些特性我们可以看出Fusion Tree单次操作的时间复杂度是$O( \log _w(n) + \log w) = O( \log n/\log w +\log w)$的，比$O( \log n )$低。 但是由于其实现方式，Fusion Tree每次对内部节点的更新复杂度是$O( B^4 )$的。 为了控制Fusion Tree均摊的更新复杂度，我们将这棵B-Tree的每对叶子节点之间的部分替换为一个大小大约为$O( B^4 )$的Weight Balanced Tree，只在WBT根节点发生变化的时候更新Fusion Tree的内部节点。 具体来说，我们B-Tree维护的是一个排序后的数组的分块，其中每个块都由一棵平衡二叉搜索树维护，fusion tree上只维护一个值来表示块边界，用途是指引每次插入，删除，查询在哪个块中。 可以发现这样我们把内部节点的变化次数除掉了一个$B^4$。 ## 4.压缩key的表示： 如何$O(1)$确定搜索路径上的一个节点的正确的儿子： 考虑一个B-Tree的节点，其上面包含了$k$个key，其中$B/2 \le k \le B$，记作$S={u_1,u_2,...u_k}$。 然后我们定义出$B(S)$表示"有区别的位的位置"，用人话来说就是我们把这$k$个key的trie建出来，然后所有有超过$1$个儿子的节点的高度构成的集合 （当然这里我们不用把trie建出来，只是这么解释比较直观，而且更能反映出其的一些性质）。 再定义一个集合$K(S)$，为$S$只保留$B(S)$中那些位之后的值，记作$K(S)={u'_1,u'_2,...u'_k}$，发现这个压缩操作对于原集合是保序的。 对于一个任意的$w-bit$的数$u$，我们记$u'(S)$表示$u$只保留$B(S)$中那些位，即把非$B(S)$中的位都置为$0$之后的值。 下面引理表达了一个压缩key的重要性质： ### 引理1： 设$B(S)$排序后为$c_11$ 令$C=(100...0100...0......)_2$，这里每两个$1$之间有$r-1$个$1$，$C$是一个常数。 注意到： $((100...0)_2-0)\&(1

There is a big tree in a magic forest, and children often hold gatherings under it. The tree can be seen as an undirected connected graph with $n$ nodes and $n - 1$ edges. Each node of the tree has some bottles of mineral water. Initially, node $i$ has $a_i$ bottles. Majies lives at the top of the tree. One day, he wants to remodel the tree so that it will be convenient for him to sort the empty mineral water bottles for recycling after he drinks a lot of water. Majies likes binary operations, so he will perform the following three types of operations: 1. Add $1$ to the number of mineral water bottles on every node whose distance to a node $x$ is $1$. The distance between two nodes on the tree is defined as the number of edges on the shortest path between them. 2. Drink $v$ bottles of water at node $x$. 3. Query the xor sum of the numbers of mineral water bottles on all nodes whose distance to a node $x$ is $1$. Majies has $m$ operations in total. You need to output the answer after each operation of type $3$.

The first line contains two positive integers $n, m$, which represent the number of nodes in the tree and the number of queries. Lines $2$ to $n$ each contain two integers, indicating an edge connecting these two nodes. Line $n + 1$ contains $n$ integers. The $i$-th integer indicates the initial number of mineral water bottles at node $i$. Lines $n + 2$ to $n + m + 1$ each start with an integer $opt$ representing the operation type. If $opt = 1$ or $opt = 3$, then an integer $x$ follows, indicating the node that Majies operates on. Otherwise, two integers $x, v$ follow, indicating the node that Majies operates on and the number of bottles he drinks.

For each operation of type $3$, output one line containing one integer, which is the answer.

Idea: dangxingyu, Solution: dangxingyu, Code: dangxingyu, Data: dangxingyu. For $30\%$ of the testdata, $n \le 10^3$, $m \le 10^3$. For $60\%$ of the testdata, $n \le 10^5$, $m \le 10^5$. For another $10\%$ of the testdata, there exists a node such that the distance from every node to this node is $\le 1$. For $100\%$ of the testdata, $1 \le n \le 5\times 10^5$, $1 \le m \le 5\times 10^5$, $0 \le a_i \le 10^5$, $1 \le x \le n$, $opt\in\{1,2,3\}$. It is guaranteed that the number of mineral water bottles at each node is non-negative at any time. Friendly reminder: mineral water bottles are neither dry waste nor wet waste; they are recyclable waste. Translated by ChatGPT 5