人类只能做到 $\widetilde O((n + q) \sqrt n)$？玩的太差了！可以做到 每次操作最坏 $O(\log^2 n)$，不依赖均摊分析或随机化。预处理时间为 $O(n\log n + q)$，空间为 $O(n\log n +q)$。

关键突破是：不再显式维护数组，而把数组表示成优先队列的弹出序列。一条可能修改 $\Theta(n)$ 个位置的交换链，只需要修改两条历史插入记录。

把整条交换链变成两次编辑

先处理不跨环的操作 $[l,r]$。跨环时依次处理 $[l,n]$、$[1,r]$，传递第一段的输出即可；$l=r$ 时只访问一个位置。这与题目规定一致。

给全部 $n+q$ 个盘子分别编号，按照“价格、编号”排序，得到互不相同的整数键。相同价格的盘子额外交换只会改变身份，不会改变任何价格，因此可以直接比较这些键。以下默认所有键互不相同。

建立一条有 $n$ 个时刻的优先队列时间线。时刻 $i$ 先执行分配到这里的全部插入，再执行一次 delete-min。把第 $i$ 次弹出的键定义为当前的 $a_i$。

最初，将原来的 $a_i$ 插入时刻设为 $i$。于是每个时刻都是插入一个键后立即弹出，显然表示了初始数组。之后，同一时刻可以有多个插入，也可以没有插入；我们始终保存每个在场盘子的插入时刻。

考虑操作 $(l,r,x)$，令 $M$ 为当前 $a_l,\ldots,a_r$ 中的最大键。如果 $x\ge M$，数组不变，输出 $x$。否则，执行：

删掉 $M$ 原来的插入记录，在时刻 $l$ 新增 insert(x)，输出 $M$。

注意，删除的是 $M$ 的插入记录，不是在某个时刻额外执行一次删除。

为什么这恰好实现了原操作？设旧数组中 $a_j=M$，其中 $l\le j\le r$。

在时刻 $l$ 之前，删除 $M$ 的插入记录不会改变弹出结果：如果它已经插入，它原本一直待在队列里，直到时刻 $j$ 才被弹出，因此不可能影响此前的最小值。

从时刻 $l$ 开始，新时间线多了一个携带中的键 $c$，初始为 $x$。对于每个 $i< j$，旧时间线弹出 $a_i$，新时间线则弹出 $\min(a_i,c)$，留下 $\max(a_i,c)$ 继续参与后面的操作。这正是题目的比较交换。

到时刻 $j$ 时，旧时间线本来弹出 $M$；新时间线没有 $M$，而是弹出携带到这里的 $c$。此后两个队列完全相同。原操作此时携带的值已经变成区间最大值 $M$，也不会再交换。

例如，对 $(3,8,5,10,7)$ 执行输入为 $2$ 的全区间操作，只需删除 $10$ 的插入记录，再在时刻 $1$ 插入 $2$，新的弹出序列就是 $(2,3,5,8,7)$。

因此，我们只剩下两个任务：修改历史插入记录，以及查询一段弹出结果的最大值。

用两个集合概括一段时间线

在时间轴上建立线段树。对每个节点，考虑从空队列开始，只执行这个节点所代表的时间区间，维护 $N$ 为最终剩余的键集合，$D$ 为期间被弹出的真实键集合。空队列上的弹出记为一次缺额；若节点长度为 $s$，缺额数就是 $z=s-|D|$。

按时间区间维护“剩余集合”和“已删除集合”，也是可追溯优先队列中使用的一种摘要方式。下面直接实现本题需要的维护操作，不把这种数据结构当成黑盒。([Erik Demaine][1])

设左右孩子分别为 $A,B$。左侧结束后，会把 $N_A$ 带入右侧。令 $W=N_A\cup D_B$，以及 $k=\max(0,|N_A|-z_B)$。将 $W$ 中最大的 $k$ 个键放入 $H$，剩余键放入 $L$，则父节点满足 $N=N_B\cup H$、$D=D_A\cup L$。

这里的含义是：右侧原来能够保留下来的 $N_B$，在额外带入一些键后仍然会保留下来。额外的键只会与右侧原本弹出的键竞争；补足缺额后，竞争者中较大的键留下，较小的键被弹出。

更严格地说，可以暂时将右侧的每次空弹出视为弹出一个 $+\infty$。带入一个额外键，就会沿右侧原来的弹出序列进行比较交换；带入多个键后，等价于从 $N_A\cup D_B$ 加上这些无穷大占位符中，选出较小的键作为弹出结果。最后去掉无穷大占位符，恰好得到上述公式。

因此，每个内部节点维护四个有序集合：$N,D,L,H$。其中 $L,H$ 只是辅助维护 $W$ 的有序划分，始终满足 $L$ 中所有键小于 $H$ 中所有键。

关键是一次历史插入编辑，只会改变一个节点摘要中的常数个成员。

考虑新增一条 insert(x)。和旧执行过程比较，新队列始终只是多携带一个键。遇到弹出操作时，这个键可能与旧弹出值交换。如果最终仍有额外键 $y$ 留下，那么 $N$ 只增加 $y$，$D$ 增加 $x$、删除 $y$；如果额外键被某次原来的空弹出消耗，则 $N$ 不变，$D$ 只增加 $x$。删除插入记录是完全相反的过程。

所以，一次编辑在任意节点上，至多产生三条集合成员变化。 虽然弹出序列可能改变很多位置，但摘要不会。

沿线段树向上更新时，左孩子的 $N$、右孩子的 $D$ 的变化进入辅助集合 $L,H$；左孩子的 $D$ 直接影响父节点的 $D$，右孩子的 $N$ 直接影响父节点的 $N$。处理完这些变化后，重新计算 $k$，在 $L,H$ 的边界移动元素，使 $|H|=k$。

孩子传来的变化只有常数条，而且 $k$ 的变化至多为 $1$，因此边界也只需要移动常数个元素。代码中的两个 while 并不是依赖均摊的循环：每次更新在一个节点上只会执行常数次。

所有有序集合用压缩二进制 Trie，也就是 Patricia Trie 实现。设 $w=\lceil\log_2(n+q)\rceil$，它的高度至多为 $w$，插入、删除、取最小值都需要最坏 $O(w)$ 时间；同时，一个包含 $s$ 个键的集合只需要 $O(s)$ 空间，而不是普通动态开点 Trie 的 $O(sw)$。

于是，一条历史插入记录的编辑需要最坏 $O(\log n\cdot w)$ 时间。

查询时，所有字典同步下降

还需要在同样的复杂度内求出弹出序列的区间最大值。

固定一个阈值 $v$，只关心不大于 $v$ 的键。对于某个节点，记 $n_v=|N\cap(-\infty,v]|$、$d_v=|D\cap(-\infty,v]|$，节点长度为 $s$。假设进入该节点时，队列中有 $c$ 个不大于 $v$ 的键，那么这一段中不大于 $v$ 的弹出结果共有 $\min(s,c+d_v)$ 个，而段末剩余数量为

$$ c'=n_v+\max(0,c+d_v-s). $$

这是刚才合并公式的计数版本：$N$ 中的键直接保留，进入节点的小键与 $D$ 中的小键竞争这 $s$ 次弹出。

将 $[1,l-1]$ 和 $[l,r]$ 分别拆成线段树节点，按时间顺序排列，总共只有 $O(\log n)$ 个。从 $c=0$ 开始，对于前缀节点，只更新 $c$；对于查询区间的节点，还检查是否有 $c+d_v\ge s$。所有查询区间节点都满足这个条件，当且仅当 $a_l,\ldots,a_r$ 全部不大于 $v$。

直接对 $v$ 二分，每次重新在各个有序集合中求排名，会得到三层对数。我们需要再消掉一层。

所有集合都使用同一个整数值域上的二进制 Trie，因此可以让这些 Trie 同时沿答案的二进制位下降。

假设当前正在确定第 $b$ 位。对于每个集合，保存当前值域区间对应的 Trie 根，以及已经确定小于该值域区间的元素个数。测试答案是否在左半边时，这个集合不超过中点的元素数量，就是“已经累计的数量，加上当前左子树大小”，只需要 $O(1)$ 时间。

拿到各节点的 $n_v,d_v$ 后，按上面的转移扫描一遍，判断答案应该走左边还是右边。随后让所有 Trie 一起走相应的分支；走右边时，将左子树大小累加进计数。压缩 Trie 在当前位没有分叉时，将它视为一个儿子为空、另一个儿子仍为自身即可。

这样，每一位只花 $O(\log n)$ 时间，共 $w$ 位，区间最大值查询也是最坏 $O(\log n\cdot w)$。这里没有对不同阈值分别模拟：不同阈值共享同一批 $N,D$ 集合，查询只是沿这些集合同步下降。

一次原操作至多进行两次区间最大值查询和四次历史插入编辑，因此每次操作最坏 $O(\log(n+1)\log(n+q+1))$。

初始化时，每个节点的 $N$ 为空，$D$ 就是该区间的初始键集合。逐层归并有序键，并在线性时间内建立压缩 Trie，总共需要 $O(n\log(n+1))$。价格不超过 $10^9$，代码使用四轮稳定基数排序，在 $O(n+q)$ 时间内完成初始编号排序。

任意时刻只有 $n$ 个在场盘子。每个盘子在一层线段树中最多出现在常数个集合里，因此所有字典共占 $O(n\log(n+1))$ 空间，加上询问和编号数组，得到总空间 $O(n\log(n+1)+q)$。