考虑 $s = 1; t = n$ 的情况，此时每次操作相当于删除序列中的最小值，然后插入某个数。这可以用优先队列简单维护。

我们考虑分块。设块的大小为 $k$。每个块我们维护一个堆，堆中的元素为块内的所有数。现在如果某个块左边来了一个新的数 $x$，那么我们把它和堆顶的元素交换，同时维护一下堆。这样我们就能够在 $O(\log n)$ 的复杂度内解决对于整块的修改操作了。

现在我们的问题就是，怎么样处理对于块内的修改操作。由于对于整块的修改操作我们只维护了一个堆，我们并不知道堆中的元素在块内的哪个位置，因此我们要设法把位置这个信息还原出来。

我们把对于整块的修改操作看成对这个块的一个标记。现在假设我们要对块 $i$ 内的某些元素进行修改，那么我们假设块 $i$ 当前有 $m$ 个标记，依次为 $t_1; t_2; \cdots ; t_m$。而上一次释放标记后块内的所有数为 $a_1; a_2; \cdots ; a_k$。每个块我们维护一个堆，堆中的元素为块内的所有数。

此时如果我们枚举所有标记，然后再对块内的数进行修改，那么时间复杂度就会退化成暴力级别。注意到我们的问题有着比较好的对称性：如果我们把寿司看成顾客，顾客看成寿司，那么我们的修改操作是类似的，同样可以用堆来维护。那么我们不妨把块内的数看成标记，把标记看成块内的数，然后用一个堆维护所有的标记，枚举块内的每一个数并用堆求出这个数会变成哪个标记。这样单次下放标记的时间复杂度变成了 $O(k \log q)$。因此总的时间复杂度为：$O(q (k \log q + \frac nk \log n))$。取 $k = \sqrt{\frac{n \log n}{\log q}}$，总的时间复杂度即为 $O(q \sqrt{n \log n \log q})$。可以大力归并优化到 $O(q\sqrt{n \log n})$，但没必要。