题目背景
题目背景和题意无关,可以跳过
1.前言:
Brodal queue 在 1996 年由 Brodal 提出,是第一个满足每个操作都 worst case 而且达到了基于比较的堆的下界的数据结构
这里给出的 Brodal queue 是一个小根堆
该数据结构的一些特性:
- 维护了两棵树。
- Brodal queue 是一种 violation heap,即允许存在一些节点不满足堆性质。
- 实现真的很复杂,常数真的很大。
2.一些记号:
Brodal queue 维护了两棵树 T1 , T2,他们的根是 t1 和 t2。
定义:
p(x):x 的父亲节点,默认 x≠t1 且 x≠t2。
rank(x):和 log(subtreesize) 相关的一个权值。
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≥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)≥2。
S4. n(x,i) 只可能为 0,2,3,4,5,6,7 中的元素。
S5. 当 T2≠null 时 rank(t1)≤rank(t2)。
解释:
S1. 边界定义。
S2. rank 构成大根堆。
S3. 一个点有至少两个孩子的 rank 是其 rank−1,所以 x 的子树大小关于 x 的 rank 至少是指数级的,所以 rank 最多是 O(logn) 的。
S4. n(x,i) 有 O(1) 上界,非 1 ,而总共有 O(logn) 种 rank,所以每个节点的度数都是 O(logn) 的。
S5. 要么 T1 比 T2 小,要么 T2 为空。
V 和 W 列表的性质:
O1. t1 是所有元素中的最小元。
O2. 如果 y 在 V(x) 或者 W(x) 中,则 x≤y,即这个元素在被插入列表时是违背了堆性质的。
O3. 如果 y<p(y) ,那么存在一个 x 使得 x≠y,y 属于 V(x) 或 W(x),即所有违背堆性质的节点都在某个节点的 V 或 W 列表中。
O4. 对于所有 x,有 w(x,i)≤6。
O5. 记 V(x)=(y|V(x)|,...,y2,y1) , 则 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。
有两个重要的性质:
给一个位置 x ,我们可以最坏复杂度 O(1) 找到 x 所属于的块内最左边的元素, 并且——
我们可以最坏复杂度 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 操作,输出一行一个整数表示答案。
样例数据
样例输入
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
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。