[Ynoi2010] Brodal queue
题目背景
题目背景和题意无关，可以跳过
## 1.前言：
Brodal queue 在 1996 年由 Brodal 提出，是第一个满足每个操作都 worst case 而且达到了基于比较的堆的下界的数据结构
这里给出的 Brodal queue 是一个小根堆
该数据结构的一些特性：
1. 维护了两棵树。
2. Brodal queue 是一种 violation heap，即允许存在一些节点不满足堆性质。
3. 实现真的很复杂，常数真的很大。
## 2.一些记号：
Brodal queue 维护了两棵树 $T1$ , $T2$，他们的根是 $t1$ 和 $t2$。
定义：
$p(x)$：$x$ 的父亲节点，默认 $x \neq t1$ 且 $x \neq t2$。
$rank(x)$：和 $log( subtree\;size )$ 相关的一个权值。
$n(x,i)$：$x$ 的孩子中满足其 $rank$ 为 $i$ 的个数。
$w(x,i)$：$W(x)$ 中 $rank$ 为 $i$ 的元素个数。
$V$ 和 $W$ 列表：维护所有违反堆性质的节点。
## 3.概述：
每个曾经作为 $T1$ 的根的点都维护 $V$ 和 $W$，我们用 $V(x)$ 表示 $x$ 节点的 $V$ 集合，$W(x)$ 表示 $x$ 节点的 $W$ 集合。
$V$ 维护的是 $rank \ge rank(t1)$ 的节点，$W$ 维护的是 $rank<rank(t1)$ 的节点，这个是对插入当时的情况成立的，也就是说在经过结构修改操作之后不一定还满足这个性质。
$V$ 是只加不删的， $W$ 是需要维护平衡的，所以只需要保证 $t1$ 的 $W$ 中的点的 $rank<rank(t1)$。
有以下的一些性质：
$rank$ 的性质：
S1. 叶子节点的 $rank$ 为 $0$。
S2. $rank(x) < rank( p(x) )$。
S3. 如果 $rank(x) > 0$，则 $n(x,rank(x)-1) \ge 2$。
S4. $n(x,i)$ 只可能为 ${0,2,3,4,5,6,7}$ 中的元素。
S5. 当 $T2 \neq null$ 时 $rank(t1) \leq rank(t2)$。
解释：
S1. 边界定义。
S2. $rank$ 构成大根堆。
S3. 一个点有至少两个孩子的 $rank$ 是其 $rank-1$，所以 $x$ 的子树大小关于 $x$ 的 $rank$ 至少是指数级的，所以 $rank$ 最多是 $O( \log n )$ 的。
S4. $n(x,i)$ 有 $O(1)$ 上界，非 $1$ ，而总共有 $O( \log n )$ 种 $rank$，所以每个节点的度数都是 $O(\log n )$ 的。
S5. 要么 $T1$ 比 $T2$ 小，要么 $T2$ 为空。
$V$ 和 $W$ 列表的性质：
O1. $t1$ 是所有元素中的最小元。
O2. 如果 $y$ 在 $V(x)$ 或者 $W(x)$ 中，则 $x \leq y$，即这个元素在被插入列表时是违背了堆性质的。
O3. 如果 $y<p(y)$ ，那么存在一个 $x$ 使得 $x \neq y$，$y$ 属于 $V(x)$ 或 $W(x)$，即所有违背堆性质的节点都在某个节点的 $V$ 或 $W$ 列表中。
O4. 对于所有 $x$，有 $w(x,i) \leq 6$。
O5. 记 $V(x) = (y_|V(x)|,...,y_2,y_1)$ , 则 $rank(y_i) \ge floor((i-1)/α)$，$α$ 是一个常数。
解释：
O1. 我们要 $O(1)$ 求出最小值，所以规定了最小元是 $t1$。
O2. $x$ 被插入的时候是被插到 $V(t1)$ 或者 $W(t1)$ 中。
O3. 违反堆性质的点一定在另一个点的 $V$ 或者 $W$ 集合中。
O4. $w(x,i)$ 有常数上界，所以 $V$ 和 $W$ 列表的大小是 $O( \log n )$ 的。
O5. $V$ 列表中的 $rank$ 有一个阶梯的下界。
对于 $t1$，$t2$ 的额外性质：
R1. 对 $i = 0 \sim rank(tj) - 1$，有 $n(tj,i) \ne 0$。
R2. $|V(t1)| \leq α \times rank(t1)$ ，和前面提到的是同一个 $α$。
R3. 如果 $y$ 属于 $W(t1)$ 则 $rank(y)<rank(t1)$。
解释：
R1. 对于 $t1$，$t2$，每个 $rank$ 的孩子至少有 $2$ 个。
R2. $V(t1)$ 的大小 $|V(t1)|$ 有 $α \times rank(t1)$ 的上界。
R3. 属于 $W(t1)$ 的点比 $t1$ 小。
R2+O5可以推出如果 $t1$ 的 $rank$ 增大 $1$ ，我们就可以增加 $α$ 个大的违反堆性质的节点，把他们加入 $V(t1)$，并且不违反 $O5$。
每次 DECREASEKEY 时 ，我们直接加一个新的违反堆性质的点到 $V(t1)$ 或者$W(t1)$。
为了避免有太多的违反堆性质的节点，我们递增地做两种不同的变换，主要为了维护 R2 和 O4 性质。
第一种：把 $t2$ 的儿子移动进入 $T1$ ，变成 $t1$ 的孩子，使得 $rank(t1)$ 变大。
第二种：通过把 $2$ 个 $rank$ 为 $k$ 的违反堆性质的节点换成了 $\leq 1$个$rank$ 为 $k+1$ 的违反堆性质的节点，从而减少 $W(t1)$ 的大小。
Note：我们这里用到了很多可变长数组，默认可变长数组是严格 $O(1)$ 的，这个是平凡的所以不详细讲怎么实现了。
这里给出了一个作者称为 guide 的数据结构的实现。
## 4.Guide Data Structure：
用途：维护 $R1$，$O4$ 性质，即对 $n(t1,i),n(t2,i),w(t1,i)$ 的上界进行维护，大概是一个维护 $O(1)$ 进位的东西。
抽象出这部分要维护的东西，也就是我们这里讲的 guide 数据结构是要维护什么：
维护：一个长为 $k$ 的 int 数组，$x_k,x_{k-1},...x_1$ （这里我们从右往左写序列）。
需要满足：$max(x_i) \leq T$ , $T$ 是预设的一个阈值常数。
我们只能在这个数组上实现 REDUCE(i) 的操作，即 $x_i$ 至少减少 $2$，$x_{i+1}$ 至多增加 $1$（实际上这里我们 $x_i$ 只能减少 $2$ 或者 $3$，$x_{i+1}$ 只能增加 $0$ 或者 $1$）。
每次可能发生对一个任意位置 $i$ 的 $x_i$ 的 $+1$ 或者 $-1$ 操作，每次操作之后我们被允许通过 $O(1)$ 次 REDUCE 操作，使得我们需要维护的数组仍旧满足性质。
guide 干的事情就是 guide（向导） ，也就是说告诉我们要做什么样的 REDUCE 操作使得这个数组仍旧满足性质。
定义 $x'$ 是 $[T-2,T]$ ，当 $x_i$ 碰到进入 $x'$ 的范围之前我们不考虑对其进行调整。
不妨设 $T=2$，我们对 $T=2$ 维护这个 guide 即可。
把原序列分成一些块，考虑形如 $2$ $1*$ $0$ 这样的连续段，不在段内的元素只可能是单独的 $0$ 或 $1$。
对每个块我们新建一个节点，然后段内的每个元素都指向这个节点。
每个节点上记录块的开头位置。
不在块内的节点直接指向一个 null。
这里我们多个点共用一个 null ，存在多个 null。
有两个重要的性质：
1. 给一个位置 $x$ ，我们可以最坏复杂度 $O(1)$ 找到 $x$ 所属于的块内最左边的元素，
并且——
2. 我们可以最坏复杂度 $O(1)$ 销毁掉一个给定的块，直接把那个存有值的点改成 null 即可。
这里写一下变换是如何实现的，由于是按照自己的理解写的，所以可能和原论文
有出入。
注意到我们可以 $O(1)$ 拆掉一个块。
前驱不在块内：
```
case1：
0 0
0 1
trivial
```
```
case2：
0 1
0 2
1 1
trivial
```
```
case3:
0 [2 1* 0]
0 [3 1* 0]
1 [1 1* 0]
拆掉这个块
1 1 1* 0
```
```
case4:
1 0
1 1
trivial
```
```
case5:
1 1
1 2
[2 0]
trivial
```
```
case6:
1 [2 1* 0]
1 [3 1* 0]
2 [1 1* 0]
[2 1 1* 0]
```
前驱是块尾：
```
case7:
[2 1* 0] 0
[2 1* 0] 1
trivial
```
```
case8:
[2 1* 0] 1
[2 1* 0] 2
[2 1* 1] 0
[2 1* 1 0]
```
```
case9:
[2 1* 0] [2 1* 0]
[2 1* 0] [3 1* 0]
[2 1* 1] [1 1* 0]
拆后面的块
[2 1* 1] 1 1* 0
拆前面的块
2 1* 1 1 1* 0
递归成块外的1加1的情况case 2,5,8
```
前驱在块内：
```
case10:
[2 1* 0]
[2 1* 1]
拆块
2 1* 1
递归成块外的1加1的情况case 2,5,8
```
```
case11:
[2 1* 1 1* 0]
[2 1* 2 1* 0]
拆部分块，通过把指针指到第二个2的位置
2 1* [2 1* 0]
递归成块外的1加1的情况case 2,5,8
```
注意到这里 $2$ 是单调向右走的，除了每次操作可能可以往左边走一格，所以把一个块端点往右移动一段，或者向左移动 $O(1)$ 个位置是可行的。
加个内存池，我们需要的空间不超过 $O(k)$。
（*可能可以四毛子优化一下？）
## 5.link 和 delink
这个是两个基本操作，用于调节 Brodal queue。
link：
假设我们有 $3$ 个节点 $x_1,x_2,x_3$ ，这三个节点不是根，且有相同的 $rank$。
经过 $O(1)$ 次比较之后，不妨我们设 $x_1$ 是这三个中最小的。
然后我们可以把 $x_2$，$x_3$ 变成 $x_1$ 的最左儿子（因为是链表，只能在头插入），并且 $x_1$ 的 $rank$ 自增 $1$。
然后 $x_2$ 和 $x_3$ 都不是违反堆性质的节点，并且 $x_1$ 仍然满足所有 S1-S5 和 O1-O5 的性质。
delink：
对一个点 $x$ ，如果 $n(x,rank(x)-1)$ 是 $2$ 或者 $3$，那么把 $x$ 的 $rank$ 为 $rank(x)-1$ 的孩子和父亲的边断开，把它"切出来"，然后 $rank(x)$ 变成剩余孩子中的 $max(rank)+1$，这里切出来之后怎么办需要特殊说明。
如果 $n(x,rank(x)-1) \ge 4$，那么把 $2$ 个 $rank$ 为 $rank(x)-1$ 的孩子切出来。
delink 一个根节点的 $rank$ 为 $k$ 的树总是会得到 $2$ 或者 $3$ 个根节点的$rank$ 为 $k-1$ 的树，和一个额外的根节点的 $rank \leq k$ 的树（这个树根节点的 $rank$ 可以是 $[0,k]$ 的任意数）。
考虑如何维护 $t1$ 的孩子，使其满足R1（ $t1$ 对于 $[0,rank(t1)-1]$ 中每个 $rank$ 有$[2,7]$个孩子）。
对 $[0,rank(t1)-3]$ 中每个 $rank$ 的孩子个数，使用两个guide，一个处理个数在 $[2,4]$ 的孩子保证其个数 $ \ge 2$，一个处理个数在 $[5,7]$ 的孩子保证其个数 $\leq 7$。
对于 $rank$ 为 $rank(t1)-1$ 和 $rank(t1)-2$ 的孩子需要特判处理。
对 $t1$ 的孩子用两个 guide 来维护,设其为 guide1 和 guide2。
guide1 维护的是 $rank$ 在 $[T-2,T]$ 中的孩子，guide2 维护的是 $rank$ 在$[2,4]$ 中的孩子，这里我们令 $T=9$，是一个常数。
我们用 guide 中的元素 $a_k$ 代指这个 guide 里面 $rank$ 为 $k$ 的节点个数。
link 操作会让 guide1 里面的一个元素 $a_k$ 减少 $3$ , 另一个元素 $a_{k+1}$ 增加 $1$ ，注意到这里我们维护的是一个上界的形式，所以减少 $3$ 和减少 $2$是类似的。
delink 操作会让 guide2 里面的一个元素 $a_k$ 减少 $1$, $a_{k-1}$ 增加 $2$ 或 $3$ , 还会多出一个 $rank$ 在 $[0,k]$ 中的元素，这里维护的是下界形式，所以只用考虑 $+2$。
注：这里其实 $-3$ 会比 $-2$ 容易破坏下界，$+3$ 会比 $+2$容易破坏上界，把 $T$ 改成 $10$ ，或者加一些特判之后这个问题可以被解决，所以不专门讨论这两种情况了。
注：这里原论文给的界是 $T=7$ ，但是我们不知道如何达成，所以在这里讲$T=9$ 的情况。
$t1$ 新增孩子：
如果导致同 $rank$ 的孩子数 $=9$ ，则从处理上界的 guide 得到需要执行的 $O(1)$ 次 reduce 操作（这导致了 guide 的实现的微小变化），对应于用 link 合并 $3$ 个 $rank$为 $k$ 的孩子，得到 $1$ 个 $rank$ 为 $k+1$ 的孩子。
注意此时孩子数减少 $3$ 后变成 $6 > 4$ ，不影响处理下界的 guide。
如果这导致 $rank$ 为 $rank(t1)-2$，$rank(t1)-1$ 的孩子过多，同样用 link 操作进行调整，这时就可能需要增加 $t1$ 的 $rank$ 了。
这里由于我们每次都是把"切出来"的节点变成 $t1$ 的孩子，所以不产生额外的违反堆性质的节点。
$t1$ 删除孩子：
类似于新增孩子，但此时 reduce 对应于 delink 操作（这里只考虑 $rank=k$ 的树变为 $rank=k-1$ 的 $2$ 或 $3$ 棵树），delink 产生的额外的 rank 不固定的树会在删除孩子完成之后被新增为 $t1$ 的孩子。
关于这里的常数 $T$ 的解释：
我们考虑一个 guide 中维护的元素到了和这个 guide 的界差 $1$ 的情况才需要
REDUCE ，不然不需要。
对于 guide1，这个界限就是 $T-1$，对于 guide2，这个界限就是 $3$。
然后我们要让这次 REDUCE 之后不会导致另一个 guide 需要调整。
所以 $T-1\;-\;3 > 4$，$3 + 3 < T-2$，可以解出 $T > 8$，故取 $T=9$。
这里和原论文的 $T=7$ 不一样，但也只是常数差别，不会对复杂度和正确性产生影响，所以不仔细讨论这个了。
对于 $t2$ 的新增/删除孩子，情况和 $t1$ 类似，不同之处是 delink 产生了 $O(1)$ 个新的破坏堆性质的点，这部分的详细内容会在后面提到。
定义 $pv$ 集合为 $V$ 集合和 $W$ 集合的并集，即潜在的违反堆性质的点的集合。
设计一个变换，用于减少 $pv$：
这一段是 $W(t1)$ 的 guide 的 REDUCE 的方法，这个变换将 $pv$ 减少了至少 $1$：
假设 $x1,x2$ 是潜在的违反堆性质的点，满足 $k=rank(x1)=rank(x2)<rank(t1)$，且 $x1,x2$不是根或根的孩子。
首先检查 $x1,x2$ 是否满足堆性质，若满足则从 $V$ 或 $W$ 列表中移除，否则：
若 $x1,x2$ 不是兄弟：
不失一般性，设 $p(x1) \leq p(x2)$，交换 $x1$ 所在子树和 $x2$ 的某个$rank=k$ 的兄弟 $x3$（由 S4 性质可知这样的 $x3$ 一定存在）所在子树（此操作不会增加 $pv$，$x1$ 仍是 $pv$，$x3$ 可能从 $pv$ 变为非 $pv$ 也可能状态不变），之后可设 $y=p(x1)=p(x2)$。
若存在 $rank=k$ 的第三个兄弟，则将 $x1$ 移除并新增为 $t1$的孩子，这样 $y$ 的 $rank=k$ 的儿子减少了一个，而且至少为 $2$ 个，不违反 S4 性质。
若不存在 $rank=k$ 的第三个兄弟，则将 $x1,x2$ 移除并新增为 $t1$ 的孩子，这样 $y$ 的 $rank=k$ 的儿子个数变成 $0$ 了，不违反 S4 性质。
若 $rank(y)=k+1$ 则还需要移除 $y$，更新 $y$ 的 $rank$，并新增 $y$ 为 $t1$的孩子，$y$ 子树原先的位置被从 $t1$ 移除的一个 $rank=k+1$ 的子树代替。
（这可能增加一个违反堆性质的点（需要加入 $W(t1)$ 中），但同时 $x1,x2$
由于父亲变成了 $t1$，所以将符合堆性质），这里还需要对 $W(t1)$ 的 guide 进行一个 $rank=k+1$ 的位置 $+1$ 的操作。
所以至少减少 $2$ 个 $pv$ 中的点，至多增加 $1$ 个点到 $pv$ 中。
（由于 S2 性质保证了等 $rank$ 替换时，被替换的点和用于替换的点没有祖先关系，因此不会成环）
避免过多的违反堆性质的点出现：
当新增一个违反堆性质的点 $x$ 时，若 $rank(x) \ge rank(t1)$ 则将其加入到 $V(t1)$ 中，否则加入到 $W(t1)$ 中。
对 $W(t1)$ 也开个 guide，里面第 $i$ 个元素就是 $w(t1,i)$。
向 $W(t1)$ 加点时，插入一个点 $k$ 时，让 guide 中的第 $k$ 个元素 $+1$，然后通过 guide 得到需要进行的 reduce(k) 操作。
在 $w(t1,k)=6$，且其中至少 $2$ 个不是 $t2$ 的孩子时，执行上述变换减少 $pv$。
若有超过 $4$ 个是 $t2$ 的孩子，则将多出的点切下并新增为 $t1$ 的孩子（这不影响 $W(t2)$ 的 guide）。
每次进行优先队列操作时：
若 $T2$ 非空，则通过将 $O(1)$ 个孩子从 $t2$ 移到 $t1$，使 $t1$ 的 $rank$ 增加至少 $1$，这使得我们可以支付 $V(t1)$ 新增的不超过 $α$ 个 $pv$。
具体地，若 $rank(t2) \leq rank(t1)+2$，则把 $t2$ 的 $rank$ 最大的孩子切下并新增为 $t1$ 的孩子，最终当 $t2$ 没有孩子的时候，把 $t2$ 新增为 $t1$ 的孩子。
若 $rank(t2)>rank(t1)+2$，则切下 $t2$ 的一个 $rank$ 为 $rank(t1)+2$ 的孩子，将其delink并新增为 $t1$ 的孩子。
若 $T2$ 为空，则 $V(t1)$ 不会有新增的 $pv$。
## 6.抽象数据结构
对于一个抽象数据结构——优先队列，我们可以使用 Brodal queue 实现，具体进行的操作为：
```
MakeQueue：T1=T2=null
```
```
FindMin(Q): return t1
```
```
Insert(Q,e): 转为Meld(Q,{T1=e,T2=null})
```
```
Meld(Q1,Q2):
不失一般性，设 $Q1.t1<Q2.t1$。
若 Q1.T1 的 rank 最大，则把其余的 $3$ 棵树新增为 Q1.t1 的孩子，Q1.T2 设为空，这个过程中不产生新的 $pv$
否则让 Q1.T2，Q2.T2 中 rank 最大的树成为新的 Q1.T2，其余的 $2$ 棵树新增为 Q1.t2 的孩子。
```
解释：如果 $min$ 所在的那个树的 $rank$ 是这四个里面最大的，那就把其他几个树都插入到 $min$ 所在的那个树的孩子里面，新的树里面 $T2$ 为空
否则 $rank$ 最大的那个树成为新的 $T2$，除了 $min$ 所在的树都插入这个的孩子里面，$min$ 所在的树成为 $T1$
```
DecreaseKey(Q,e,e'):
修改权值后检查是否违反堆性质
如果违反堆性质，则将其加入pv中，此时pv大小+1
然后按前文避免过多的违反堆性质的点出现的方法来让pv减少至少1，使得pv大
小平衡
```
```
DeleteMin(Q):
将 t2 的孩子（O(log n) 个）全部切下，新增为 t1 的孩子；将 t2 变为 t1 的孩子；
删除 t1 得到 t1 的孩子，总共有 O(log n) 个。
遍历 t1 的孩子，V(t1) 和 W(t1)，从而得到新的最小值t1'
若 t1' 不是 t1 的孩子，则与等 rank 的孩子交换，这可能产生 O(1) 个 pv。
然后将 V(t1),V(t1'),W(t1),W(t1') 合并为 W(t1')：
先将 V(t1') 置为空，然后使用变换令 w(t1',i)<=1，最后使 t1' 成为新的 t1
```
```
Delete(Q),e: 转为DecreaseKey(Q,e,-inf),DeleteMin(Q)
```
题目描述
给定一个长为 $n$ 的序列 $a$ ，每个位置有一种颜色，有 $m$ 次操作，支持：
`1 l r x`：区间 $[l,r]$ 的数都变成 $x$。
`2 l r`：查询有多少二元组 $(i,j)$ 满足 $l \leq i < j \leq r$ ，且 $a_i = a_j$。
本题强制在线，每次的 $l,r,x$ 需要 $\operatorname{xor}$ 上（上次答案 $\bmod 2^{32}$），也就是说使用 `unsigned int` 数据类型存储上次的答案即可，如果之前没有询问，则上次答案为 $0$。这里输出的答案不对 $\bmod 2^{32}$ 取模。
输入输出格式
输入格式
第一行两个整数 $n, m$。
第二行 $n$ 个整数表示序列 $a$。
之后 $m$ 行，每行形如 `1 l r x` 或 `2 l r`，表示上述的操作。
输出格式
对于每个 $2$ 操作，输出一行一个整数表示答案。
输入输出样例
输入样例 #1
10 12
6 9 9 4 7 8 10 4 9 2
2 1 4
1 0 5 0
2 3 6
2 10 9
1 7 9 2
2 7 9
1 2 7 1
1 2 11 4
2 6 10
1 3 12 0
1 14 14 15
2 7 12
输出样例 #1
1
3
0
3
6
16说明
Idea：nzhtl1477，Solution：nzhtl1477&ccz181078，Code：ccz181078，Data：nzhtl1477
注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。
对于其中 $1\%$ 的数据，为样例 1。
对于另外 $9\%$ 的数据，没有修改操作。
对于另外 $19\%$ 的数据，$n,m\leq 500$。
对于另外 $19\%$ 的数据，每次修改的区间长度不超过 $5$。
对于另外 $19\%$ 的数据，保证数据随机。
对于 $100\%$ 的数据，$1\leq n,m\leq 2\times 10^5$，$1\leq a_{i},x\leq n$，$1\leq l\leq r\leq n$。