P3960 列队题解

看上去是要维护一个二维数组，支持区间平移。但是仔细观察后你发现向下的平移只会在最后一列出现。

因此我们实际上只需要支持最后一列的向上平移，和行的向左平移即可。

平衡树做法

对于这种区间平移的问题有一种比较无脑的做法就是直接平衡树。

更具体的，我们对于每行的前 个元素和最后一列的 个元素开一颗平衡树。

每次我们删除第 行的平衡树的第 个元素，将最后一列对应的平衡树的第 个元素插入到最后。然后删除最后一列的第 个元素，将一开始删除的元素插入到最后。

然后就有了一个问题。那就是空间。我们发现 可以同时是 ，直接开就爆了。

注意到开始的数组是一个等差序列，我们可以使用颜色段均摊的技巧维护这个连续段就行了。

线段树做法

实际上，我们发现我们并不需要平衡树的任意位置插入。我们只需要能在最后插入元素即可。

因此我们或许并不需要上平衡树。

我们考虑用线段树维护。

我们需要查询第 个没有被删除的元素。这个实际上是好维护的，考虑将所有没删除的元素记作 ，删除的元素记作 ，我们实际上是要求第一个大于等于 的位置，这个是可以线段树上二分实现的。

因此我们就有了下面这个做法。，我们对于每行的前 个元素和最后一列的 个元素开一颗线段树。

将每一行线段树的前 个元素和最后一列线段树的前 个元素置 。这可以通过打一个区间加 tag 来实现。

删除的时候就将对应的位置 。在尾部插入的时候只需要在当前最后一个 后面的位置 ，然后记录一下这个位置对应的值即可。

用动态开点线段树维护，空间和时间就都是一个 了。代码量会比平衡树少一点，常数也会更小。

树状数组做法

但是动态开点线段树依旧很难写啊！

有没有更简单的写法？

我们发现，之前阻止我们优化的主要问题在于，无法同时开下 个对空间要求为 的数据结构。因此我们需要采用平衡树或者动态开点等方法来将每颗数据结构的初始空间优化到了 。

与之相对的另外一个优化想法就是，能不能只开 颗数据结构解决这个问题？

注意到题目并没有要求在线。考虑将所有查询离线。

我们注意到每行每列数据结构的操作都相对独立。

因此我们可以处理出来每颗数据结构上有哪些操作，最后逐个进行即可。

不过有一个问题，那就是如果你没有算出来前面的答案，你并不知道你具体要插入什么数。

不过仔细思考发现，你实际上并不需要知道插入的具体是什么数，你只需要知道插入的位置即可（操作中并不涉及对具体数值的操作）。因此你先用一个占位符代替一下插入的数，记录一下插入的数对应的是前面哪次询问的答案即可。

具体的，我们先考虑进行最后一列数据结构的所有操作，对于每次尾部插入的操作，我们用一个占位符 表示“这里元素的值是第 次询问的答案”。每次查询的答案插入到对应行数据结构的操作序列中。请注意这里总共的操作级别是 的。

最后我们处理出来的 ans 数组可能有两种，一种是正常的小于 的值，另一种是大于等于 的值。

我们最后按顺序处理一下答案，将所有 的元素替换成第 次询问的结果。另外由于题目限制，显然每个元素只会依赖前面询问的值，因此这里并不会出现问题。

总共只需要一颗数据结构，因此你直接树状数组即可。

维护方法类似线段树，只需要把线段树上二分换成树状数组上倍增即可。