P6019 [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 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)+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
题目描述
给定一个长为 $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}$ 取模。
输入格式
无
输出格式
无
说明/提示
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$。