[LOJ2461] 完美的队列

题目链接

题解

复杂度讨论中默认 \(n,m\) 同阶。

定义第 \(i\) 个操作的发生时间为 \(i\)

求出每次操作加入的新的 \(x\) 全部被弹出的最早时间,就很好求答案了。

从后往前考虑每个操作,计算这次操作加入的元素全部被弹出的最早时间。

定义一个队列 \(i\) 的弹出时间为从当前操作开始,往后第 \(a_i\) 个影响队列 \(i\) 的操作的发生时间。

分块,从后往前依次加入每个操作,分别维护每一块中的队列弹出时间的最大值。我们把一块中所有队列弹出时间的最大值称为这个块的最早弹出时间。

在加入第 \(k\) 个操作后,第 \(i\) 个块 \([a_i,b_i]\) 维护最早弹出时间 \(t_i\),设 \(c_p\) 为第 \(k\) 个操作到第 \(t_i-1\) 个操作中第 \(p\) 个队列被 push 的次数,维护 \(mn_k = \min_{a_i \le p \le b_i} c_p-a_p\)。同时维护 \(c_p\) 的值。(通过打标记)

考虑在加入操作 \(i\) 后,如何更新每块维护的信息。

假设这个块是第 \(k\) 个块。
对于这个块的最早弹出时间大于等于 \(m\) 的情况预先处理好。下面只讨论最早弹出时间小于 \(m\) 的情况。

更新 \(mn_k\)\(c\) 数组

如果这个块被第 \(i\) 次修改的区间完整包含:

更新 \(mn_k \leftarrow mn_k+1\)。更新 \(c_p\) 的值,即打一个整块加 \(1\) 标记。

如果这个块未被第 \(i\) 次修改的区间完整包含:

暴力重构,更新 \(mn_k\)\(c\) 数组。

更新 \(t_k\)

按以下步骤进行:

  1. 如果 \(mn_k \ge 0\),说明 \(t_k\) 可以减小,那么 \(t_k \leftarrow t_k-1\)。否则不用更新,结束操作。
  2. 如果第 \(t_k\) 次操作包含整个块,那么 \(mn_k \leftarrow mn_k-1\),打 \(-1\) 标记更新 \(c_p\) 的值。否则暴力重构更新 \(mn_k\)\(c_p\) 的值。
  3. 转到操作 1。

这样就做到了在 \(O(n \sqrt n)\) 时间内维护每个块的最早弹出时间。

剩余的问题是: 如何在从右往左加入操作的过程中,支持查询一个区间的最早弹出时间。把区间拆成若干个块和不超过 \(2 \sqrt n\) 个多出来的点。对于这些块,已经知道了它的最早弹出时间,取 \(\max\) 即可。对于这些多出来的点,需要动态询问他们的最早弹出时间。

处理单点信息

要支持从后往前添加操作,询问单个队列的最早弹出时间。

同样分块维护。对每个块开一个 vector,对每个队列开一个 vector。在进行修改时,对完整包含的每个块的 vector 加入当前修改的编号,再对两边多出的 \(O (\sqrt n)\) 个队列对应的 vector 加入当前修改的编号。

那么一个队列的操作序列就是它的 vector 和它所在的块的 vector 归并后的结果。对每个点记录它的最早弹出时间 \(t\) (每次询问时更新,修改时不一定是最新的),它的 vector 中第一个在 \(t\) 之前的修改的位置 \(p_1\),它所在块的 vector 中第一个在 \(t\) 之前修改的位置 \(p_2\)。对每个块记录这个块中的队列在上一次更新信息之后修改的次数 \(c\)。那么修改的时候对整块只需要 \(c \leftarrow c+1\),对两端的块更新其中每一个队列的 \(t, p_1, p_2\),并把 \(c\) 设为 \(0\)。更新方法大致为:对于一个队列,先判断 \(t\) 是在它 vector 中还是在块的 vector 中(通过 \(p_1, p_2\) 可以直接判断),这两种情况区别不大,所以这里只写在块 vector 上的情况。定义一个临时变量 \(t = c\),如果它的块的 vector 中的第 \(p_2+t\) 项的小于这个队列的 vector 中的 \(p_1\) 项,那么 \(p_1 \leftarrow p_1+1\),然后 \(t \leftarrow t-1\),然后再次检查,这样循环直到可以直接把 \(p_2\) 改为 \(p_2+t\) 的时候,修改 \(p_2\) 就完成了更新。

一个队列被更新时进行的判断的总次数与它的 vector 中元素个数同级,所以更新的总复杂度是 \(O(n)\) 的。(但是维护 vector 和进行操作是 \(O(\sqrt n)\) 的)。

这样就以 \(O(n \sqrt n)\) 的时间复杂度解决了问题。

实现

1
待填