参考文献

• Chris Okasaki, Purely Functional Data Structures
• Edsko de Vries, Efficient Amortised and Real-Time Queues in Haskell

题解比较详细，请大家不要慌张。

记得用读入优化了么？

被 log 卡过了

dalao 的程序在此，$\log$ 碾 $O(1)$ 好妙啊

题目在此 标程在此

题目大意

维护一个可持久化的 std::queue 类似物，支持（可持久化的） push_back 和 pop_front。

各种记号的总结

注

列表和指向链表的指针不做区分

算法 1

我们可以用平衡树维护这个队列

时间复杂度 $O(T\log T)$

算法 m

我们可以在操作树上用倍增找到队首

时间复杂度 $O(T \log T)$ 竟然卡过了

dalao 的程序在此，$\log$ 碾 $O(1)$ 好妙啊

算法 x

对于没有加密的数据，我们可以离线构建出操作树来，这样只要遍历一遍就可以得到结果。

时间复杂度 $O(T)$

算法 2

我们维护两个链表 $L$ 和 $R$，那么整个队列就是 $L + \mathtt{rev}(R)$

比如 $\langle L=1\to2\to3\to\mathtt{nil}\ |\ R=6\to5\to4\to\mathtt{nil}\rangle$ 就表示 $\langle1,2,3,4,5,6\rangle$。

那么 $\mathtt{push\_back}$ 就是往 $R$ 前面加元素，$\mathtt{pop\_front}$ 就是从 L 前面拿元素。

比如这里 $\mathtt{pop\_front}$ 出来之后就会变成 $\langle L=2\to3\to\mathtt{nil}\ |\ R=6\to5\to4\to\mathtt{nil}\rangle$

$\mathtt{push\_back}(7)$ 就会变成 $\langle L=1\to2\to3\to\mathtt{nil}\ |\ R=7\to6\to5\to4\to\mathtt{nil}\rangle$

一看就可以可持久化对吧。今天的世界也很和平。

等下，如果 $L$ 直接就是 $\mathtt{nil}$ 怎么办？

凉拌。

我们来考虑一下，如果 $L​$ 是 $\mathtt{nil}​$ 的话，那么全队列就是 $\mathtt{rev}(R)​$。那么我们可以考虑先把 $L​$ 替换成 $\mathtt{rev}(R)​$，然后再 $\mathtt{pop\_front}​$。

如果 $R$ 也是 $\mathtt{nil}$ 怎么办？我不是说过不会出现 $\mathtt{pop\_front}$ 一个空队列的情况么？

那么比如 $\langle L=\mathtt{nil}\ |\ R=7\to6\to5\to4\to\mathtt{nil}\rangle$，我们就先把它变成 $\langle L=4\to5\to6\to7\to\mathtt{nil}\ |\ R=\mathtt{nil}\rangle$ ，然后开开心心地 $\mathtt{pop\_front}$ 出一个 $4$ 来就好了。

每个元素会被 $\mathtt{push\_back}$ 进来，被 $\mathtt{rev}$ 一次，再被 $\mathtt{pop\_front}$ 出来，所以是 $O(n)$ 的。

慢着，这个分析在可持久化的情况下是错的，因为……

我们不停地给 $\langle L=\mathtt{nil}\ |\ R=7\to6\to5\to4\to\mathtt{nil}\rangle$ 进行 $\mathtt{pop\_front}$，那么这几个元素就会一遍一遍地过 $\mathtt{rev}$，结果：$O(N^2)$

算法 3

APIO 2017 讲课的时候好像说过，我们可以把重构数据结构的时间真·平摊到单个操作上。那……把 $\mathtt{rev}(R)$ 摊到 $|R|$ 次操作上好了。

但是不太妙的是 $\mathtt{pop\_front}$ 的时候我们需要回答开头的元素啊。我们可以一般化重构的操作，不一定在 $L=\mathtt{nil}$ 的时候重构，而是可以提前：

$$ \langle L=A\ |\ R=B\rangle \Longrightarrow \langle L=A+\mathtt{rev}(B)\ |\ R=\mathtt{nil}\rangle $$ 如果 $|A|=n$ 而 $|B|=n+1$，（这么选取使得是为了把操作凑到正好，下面就明白了）那么我们把 $A+\mathtt{rev}(B)$ 的时间摊成 $n$ 份，用一种类似 lazy 标记的思路，在链表中除了这个节点的值 $\mathtt{value}$ 和下一个节点的指针 $\mathtt{next}$ 以外，再储存额外的信息 $\mathtt{r_1}$ 和 $\mathtt{r_2}$，用 $\langle \mathtt{value}\ |\ \mathtt{next}\ |\ \mathtt{r_1}\ |\ \mathtt{r_2}\rangle$ 表示我们这个链表其实是 $\mathtt{value} \to (\mathtt{next} + \mathtt{rev}(\mathtt{r_1})+\mathtt{r_2})$。注意到 $\mathtt{rev}(m\to X)+Y=\mathtt{rev}(X)+(m\to Y)$。（别忘了 $u\to [a_1,a_2,\dots,a_n]=[u,a_1,a_2,\dots,a_n]$）我们可以这么下发 lazy 标记：

• （$\mathtt{next}\neq\mathtt{nil}$）$u\to ((v\to M)+\mathtt{rev}(z\to X)+Y) \Longrightarrow u\to v\to(M+\mathtt{rev}(X)+(z\to Y))$
• （$\mathtt{next}=\mathtt{nil}$）$u\to(\mathtt{nil}+\mathtt{rev}(\mathtt{a\to b\to nil})+Y)\Longrightarrow u\to b \to a \to Y$

下发 lazy 的过程可以参照图片（图中标的数字，是这几个元素在完全发完 lazy 标记之后的相对顺序）

不要忘了，我们创建 lazy 标记 $A+\mathtt{rev}(B)$ 的时候，有 $|A|=n$，$|B|=n+1$。如果 $A\neq \mathtt{nil}$。设 $A=u\to M$，则创建 $\langle u\ |\ \mathtt{next}=M\ |\ \mathtt{r_1}=B\ |\ \mathtt{r_2}=\mathtt{nil}\rangle$ 表示它。否则，$B$ 只有一个元素，$A+\mathtt{rev}(B)=B$。可以验证上面说的下发 lazy 标记的情况确实完整覆盖了所有可能。

注意：我们下发 lazy 标记的时候，其实确实是修改了之前版本的数据结构，但是我们并没有改变序列的内容，只改变了结构，所以没关系。

为了使得我们可以一边操作一边发 lazy，我们还需要在队列里维护一个指针 $\mathtt{cur}$ 表示我们的 lazy 发到哪儿了。

接下来，我们只要做到如下的事情，就可以成功维护队列了：

• $|L|-|R|\geq0$，保证只要队列非空我们就可以直接从 $L$ 里面 $\mathtt{pop\_front}$ 出东西来，免得浪费时间算 $\mathtt{rev}(R)$。
• 在 lazy 被发下去之前，我们不会去碰一个有 lazy 的节点

在这样的条件下，我们只要保证每次操作都是 $O(1)$ 的就保证了复杂度，这很简单。关键是怎么保证这两个条件。

我们发现，在不重构的情况下，$\mathtt{push\_back}$ 和 $\mathtt{pop\_front}$ 都会导致 $|L|-|R|$ 减小 $1$。而我们往 $\mathtt{next}$ 指针走的时候，$|\mathtt{cur}|$ 也会减小 $1$。于是我们可以直接保持 $\mathtt{cur} = |L| - |R|$。当 $\mathtt{cur} = \mathtt{nil}$ 的时候再操作，就导致 $|L|-|R|=-1$，正好该重构了。别忘了，我们的重构指的是： $$ \langle L=A\ |\ R=B\rangle \Longrightarrow \langle L=A+\mathtt{rev}(B)\ |\ R=\mathtt{nil}\rangle $$ 从版本 $v$ 生成版本 $i$ 的操作的时候：（设中间结果为 $i'$）

• （$\mathtt{v\to cur=\mathtt{nil}}$）那么此时 $|v\to A|=|v\to B|$，操作完 $|i' \to A|-|i'\to B|=-1$，此时我们重构。最终得到的 $i\to A=i\to\mathtt{cur}= \langle i'\to A\to \mathtt{value}\ |\ \mathtt{next}=i'\to A\to \mathtt{next}\ |\ X=i'\to B\ |\ Y=\mathtt{nil}\rangle$，而 $i\to B=\mathtt{nil}$。
• （$v\to \mathtt{cur}\neq \mathtt{nil}$）那么我们先给 $\mathtt{cur}$ 下发 lazy（要不然万一 $A$ 直接就是一个有 lazy 没发的节点就爆炸了），然后按照算法 2 操作。新的 $i\to \mathtt{cur}=v\to \mathtt{cur}\to\mathtt{next}$

这样我们连链表长度都不需要维护了，毕竟 $\mathtt{cur}$ 指针会告诉我们。

除了重构以外，其余可以参考算法 2 的前半部分。因为 $|L|-|R|\geq 0$，所以对于合法的操作一定不会遇到 $L=\mathtt{nil}$。

详见标程

时间复杂度 $O(T)$

算法 y

如果我们记录 $|L|$ 和 $|R|$ 来确定何时重构，并且不使用 $\mathtt{cur}$ 指针进行标记的提前下发，那么我们可能一次操作需要下发多重 lazy。但是可以证明每次操作仍然是均摊 $O(1)$ 的。

是的。

这是可持久化数据结构。均摊。

时间复杂度 $O(T)$

关于题图

肯定没有提醒你用两个链表表示队列，对吧