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

· · 题解

书接上文。

虽然但是，不能因为卡过了就不写正经做法了。

学习了 WerKeyTom_FTD 老师和 lzqy_ 老师的做法，虽然都是半懂不懂，但还是总结出了一个做法。

我原来的思路其实很对，只是后面的维护比较唐。

还是从：

扫描线从大到小枚举 L，我们需要求出 L 时刻加入的线段最后有效的时刻。（前文第十段）

出发。

原来我的思路是对于每个询问快速找到最后有效时间点，这里也差不多。但是注意到：区间最后有效时间点等于区间内各个点的最后有效时间点的 \max。

所以我们开始考虑对序列而非时间进行分块，区间答案就是整块答案和散点答案的 \max。

然后仍然是倒着扫描线。

先考虑整块。考虑 two-pointer 的策略维护整块答案。可以直接像我之前的做法一样，整块维护线段树做区间加和区间求 \min 来判断是否可行。于是这部分可以做到 O(\frac{nm\log{n}}{S})。

WerKeyTom_FTD 老师指出这是不必要的。具体的，我们把修改放到要加入/退出的线段上考虑。线段应该会覆盖不超过 \frac{n}{S} 个整块和 2S 个散点。对于整块，我们维护一个整块操作标记，对于散点，我们暴力修改对应位置。整块操作可以做到 O(1)，而散点操作在所有块维护中只会出现 O(mS) 次。此时总修改显然是 O(\frac{mn}{S}+mS) 的。

然后考虑散点。经过和 WerKeyTom_FTD 老师的讨论我了解了散点其实也可以 two-pointer。但是我的 two-pointer 有点区别（比较猎奇）。

具体的，考虑影响一个点的操作只有两种：这个点上的散点操作、这个点所在块的整块操作。

散点操作只有 O(mS) 个，如果我们对每个点维护指针并且让指针只指向散点操作复杂度就是对的。

我们在整块上记录这个整块的操作的所有位置，总信息量是 O(\frac{m^2}{S}) 的。对每个点开一个 vector 记录这个点的散点操作，并记录每个散点操作前有多少次整块操作，总信息量是 O(mS) 的

然后我们考虑一次询问一个散点。首先我们尝试指针能否移动到下一个位置，相当于减去散点间整块个数加一之后是否大于 0。可以就暴力移动指针。

否则我们得出剩下需要撤销的次数，我们能 O(1) 的找出对应的整块操作/散点操作在哪，就可以回答了。

然后就没了。将 n,m 视为同阶，上述复杂度都是 O(NS) 或是 O(\frac{N^2}{S})，可以做到 O(N\sqrt{N})。

30 pts MLE，祖传空超，但是跑得很快。

通过数组复用，块长调整得到 95 pts MLE。

块长大概 130 时散点数量和整块数量最平衡，空间最优。这份代码是我尽力卡空间的结果。

又仔细想了想。

上面的做法瓶颈主要是存下 pt、sm、bk。

想到可以对于每个块分开跑，每次只用预先计算出单个块的 pt、sm、bk，时间复杂度显然不变，只是会多 O(N\sqrt{N}) 的开销。

但是就只用存下单个块的 pt、sm、bk 了。

其实整块和散块可以开两个数组然后一起处理，但是上面为了卡空间改掉了，就不改回来了，反正时间非常充裕。

100 pts AC。

并且这一版在 LG 上也能过了！

并且这份代码也可以不用玄学块长，\sqrt{N}=317 也能过！

完结撒花。