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
题目描述
魔法森林里有一颗大树，下面经常有小孩召开法。
大树可以看做一个有 $n$ 个节点，$n - 1$ 条边的无向连通图。大树的每个节点都有若干瓶矿泉水，初始第 $i$ 个节点有 $a_i$ 瓶矿泉水。
麦杰斯住在大树顶端，有一天他想改造一下大树，方便他巨大多喝水之后可以垃圾分类矿泉水瓶。
麦杰斯喜欢二进制运算，所以他会有以下三种操作：
1. 将树上与一个节点 $x$ 距离为 $1$ 的节点上的矿泉水数量 $+1$。这里树上两点间的距离定义为从一点出发到另外一点的最短路径上边的条数。
2. 在一个节点 $x$ 上喝掉 $v$ 瓶水。
3. 询问树上与一个节点 $x$ 距离为 $1$ 的所有节点上的矿泉水数量的异或和。
麦杰斯共有 $m$ 次操作，他希望你在每次 $3$ 操作后告诉他答案。
输入格式
无
输出格式
无
说明/提示
Idea：dangxingyu，Solution：dangxingyu，Code：dangxingyu，Data：dangxingyu
对于 $30\%$ 的数据，满足 $n \le 10^3$，$m\le 10^3$。
对于 $60\%$ 的数据，满足 $n \le 10^5$，$m \le 10^5$。
对于另外 $10\%$ 的数据，存在一个点满足所有点到该节点的距离 $\le 1$。
对于 $100\%$ 的数据，满足 $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\}$。
保证任意时刻每个节点的矿泉水数非负。
温馨提示：矿泉水瓶不是干垃圾也不是湿垃圾，而是可回收垃圾。