题解：P9247 [集训队互测 2018] 完美的队列

现有题解都远远快于我的做法。

但是受限于水平不足，题解做法我一个都没想到。

只能想到一个 $O(m\sqrt{m}\log{n})$ 的做法。

但是 LOJ 上卡过了，所以写这个题解。

由于询问一直是全体区间，所以实际上是在问那些线段没有完全失效。

如果只需要维护第一条线段到最后时间是否失效，一个不那么依赖线段的思路是先将每个位置的值附为 $-a_i$，然后操作就是区间加，最后看线段所对应区间的最小值是否小于等于 $0$。这个可以用线段树简单实现。

考虑这个方案的线段其实可以撤销，也就是区间减。于是我们可以扩展到维护全体线段到最后是否失效。就是求完第一条后区间减删除第一条线段。以此类推。

或者更简单的，操作也是交换的，加入线段的时间是不重要的，倒着加入线段就好了。

现在，我们可以方便的计算出加入 $[L,R]$ 的线段后 $L$ 时刻加入的线段是否还有效，并且可以 $O(\log{n})$ 的移动 $L,R$。

扫描线从大到小枚举 $L$，我们需要求出 $L$ 时刻加入的线段最后有效的时刻。如果可以快速计算出 $R$ 时刻 $L$ 是否还有效就可以做。

感觉这个很难 polylog。

我的思路是将时间轴分块，将每个块的块尾（即每个 $kS$ 时刻）设为“哨兵”，维护 $[L,kS]$ 时的序列信息。这样对于任何 $[L,R]$ 都可以在 $O(S\log{n})$ 的时间求出。可以从 $m$ 开始，先 $O(\frac{m}{S}\log{n})$ 跳完所有的不合法整块后缀，然后 $O(S\log{n})$ 跳完不合法散点求出 $L$ 时刻的答案。

这样子就是 $O(m(\frac{m}{S}+S)\log{n})$，取 $O(\sqrt{m})$ 做到 $O(m\sqrt{m}\log{n})$。

以上是理论部分，接下来是代码实现。

直接按照上面的说法写：40 pts TLE。本地跑较大数据跑了 $8$ 秒多。

第一个比较大的优化是 $O(\sqrt{m}\log{n})$ 暴力跳完所有的不合法整块后缀的过程。这个过程我们按顺序检查每个哨兵时刻的区间最小值是否 $\leq 0$。没必要按顺序检查，可以二分加速这个过程做到 $O(\log{\sqrt{m}}\log{n})$。

理论复杂度不变，得分不变：40 pts TLE，但是本地跑较大数据跑了 $7$ 秒多。

第二个优化是线段树。经典的线段树常数过大很容易 TLE。改成使用常数非常小的 zkw 线段树。理论复杂度不变，但是本地跑较大数据跑了不到 $4$ 秒，此时块长是 $317$。

但是空间炸了：15 pts MLE。主要瓶颈在于每个块都要开一个 $2N$ 的线段树。

我们可以调大块长，牺牲时间换取空间。块长为 $635$ 的时候做到了 95 pts MLE。但是 $640$ 时变成了 70 pts TLE，搞得我有点不敢再调大块长了。

但是计算一下，一颗 zkw 线段树在 $n=10^5$ 时需要 $231073 \times 2$ 个 int（v 和 tag），$250 \times 1024 \times 1024 \div 4 \div 231074 \div 2 = 141$，当 $S=715$ 时块个数为 $140$。

发现过了 100 pts AC，非常奇妙。我的理解是空间太大导致常数太大。